時間の合計複雑度の合計

Question

私はアルゴリズムの時間の複雑さを理解しようとしており、この問題に遭遇しました。問題は、区間合計を計算することです（0 < = k < = length_of_list）。

public static void main(String args[]){ 
    LinkedList<Integer> l=new LinkedList<Integer>(); 
    l.add(4); 
    l.add(2); 
    l.add(3); 
    l.add(1); 
    l.add(5); 

    int k=2; 

    List result = new ArrayList(); 
    int n = l.size(); 

    for(int i = 0; i < n; i++){ 
     if(i >= k-1){ 
      int sum = 0; 
      for(int j = i; j >= i-k+1; j--){ 
       sum += in.get(j); 
      } 
      result.add(sum); 
     } 
    } 
    System.out.println(result); 
} 

上記のコードの時間の複雑さを教えてもらえますか？それはn * kかn^2かです（kの最大値はnなので）。条件が時間の複雑さに影響するか？

Answer 1

ifが何度もO（n）であるため、内部ループはO（n-k）回実行されます。
内部ループはO（k）です - 繰り返し回数です。

全体アルゴリズムは、O（n）* O（k）= O（n * k）です。

あなたはそれがO（n - k）* kであると主張することができますが、k < < nについてはO（n * k）と同じです。

kのサイズがnに近い場合、ifは真（O）（1）であり、内側のループはO（k）となるため複雑さはO O（n）はk〜nのため、全体的にO（n）です。