複雜性（初學者問題）

Question

這些陳述的複雜性是什麼？

for(int k = 1; k < n; k++) 
    for(int i = 0; i < n-k; i++){ 
     //O(1) operation here 
    } 

解釋讚賞。

Answer 1

首先在外環中進行操作n-1次。 第二次你去做吧n-2次，...把這些加起來，你將以(n)*(n-1)/2作業結束。

要看到這個總和，把它從1寫到（n-1），然後從（n-1）寫到1並且逐個添加每個項。

1 2 3 ... n-3 n-2 n-1 
n-1 n-2 n-3 ... 3 2 1 
--------------------------- 
    n n n  n n n 

因此2 * sum = (n-1) * n。

就複雜性而言，這大約是n²。