Big-O算法

Question

我有一個相當簡單的問題，但是我有點不確定實際的運行時間（例如Big-O）是什麼。

該程序看起來像這樣。

n <- user input 
for i=1 to n 
    foo(i) 

foo a: 
for i=1 to a 
    foo2() 

foo2做了一個近乎恆定的工作量，這並不會很重要。

這是什麼大事？

Answer 1

對於每個整數0 < = I < = n，則有另一種環，其變爲0 < = j的< = I。

因此，第i個整數需要我致電foo2()。

超過n個整數，此加起來平均（N/2）的額外調用foo2()每整數 -

n + (n - 1) + ... + 1 + 0相同

n + (n - 1 + 1) + ... + (n - n/2 + n/2)，或

n * (n/2)。

由於複雜性上限爲n^2/2,，其增長速度將快於n^2--因此複雜度爲O(n^2)。

Answer 2

（假設內部函數foo2()是Θ（1））

這Θ（N^2），這是因爲外環對所有i=1...n與內循環執行一次被迭代每外部循環迭代i倍，總計sum(i) from i=1 to n執行foo2()，相當於(n+1)*n/2 = 1/2*n^2+1/2*n次。

Θ（n^2）意味着O（n^2）。