arrays - 当i为外循环且内循环以j=i+1开始时双循环的时间复杂度

Question

我试图更清楚地了解我在下面编写的算法的复杂性:

left = 1
right = 1

for i=0; i < array.len; i ++:
        j = i+1
        for j; j < array.len; j++:
             right *= array[j]
        tmp[i] = array[idx]
        left *= array[idx]
        right = 1
return tmp

如果我们将数组大小定义为n，则外层循环的复杂度为O(n)，但内层循环并不是一直迭代n-1次，只有在i=0时才迭代第一次。

那么，复杂度是多少？ 外循环为 O(n)， 内循环的 O(n-j) ？ 那么，也许 O(n(n-j)) ？最终结果是 O(n^2)？

请帮忙。

Answer 1

是的，O(n^2) 是时间复杂度。第一个循环运行 n 次。对于第一个循环的每次迭代，第二个循环运行 n 次。 n * n = n^2