java - 区间和的时间复杂度

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)。 if 条件会影响时间复杂度吗？

Answer 1

由于 if 被执行了这么多次，内部循环执行了 O(n-k) 次，即 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)，对于 k ~ n 来说是 O(n)，所以总体上是 O(n)。