Сложность временного интервала

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

Внутренний цикл выполнен O (n-k) раз из-за if, являющегося этим много раз, что является O (n).
Внутренний цикл 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) в целом.