区间和的java时间复杂度

Question

我试图理解算法的时间复杂性，并且遇到了这个问题。问题是如何计算区间和（0<；=k<；=u列表的长度）

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），对于k~n，它是O（n），所以总体上是O（n）