區間總和的時間複雜度

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的邊緣情況，複雜度爲O（n），因爲if將爲真O（1）次，而內部循環爲O（k），即O（n）代表k〜n，所以O（n）整體。