嵌套循環的運行時間估計/大O表示

Question

我無法理解代表某些代碼中執行的操作數的函數f（x）的含義。

int sum = 0; // + 1 
for (int i = 0; i < n; i++) 
    for (int j = 1; j <= i; j++) 
     sum = sum + 1; // n * (n + 1)/2 

（請注意，在對最後的評論分子沒有2，但在以下的功能。）

然後我的筆記說，F（X）= 2N（N + 1）/ 2 + 1 = O（n^2）

我明白，因爲有兩個for循環，無論f（x）是什麼，它將= O（n^2），但爲什麼是時間估計是什麼？ j < =我給你n *（n + 1）？那麼分母中的2呢？

Answer 1

想想，在這段代碼的整個執行過程中，內循環將運行多少次。請注意，

• 當i = 0時，它運行零次;
• 當i = 1時，它運行一次;
• 當i = 2時，它運行兩次;
• 當i = 3時，它運行三次;
• ...;和
• 當我= n - 1時，它運行n - 1次。

這意味着總次數最內層循環運行由下式給出

0 + 1 + 2 + 3 + 4 + ... +（N - 1）

這是一個著名的求和並且它解決了向

0 + 1 + 2 + 3 + 4 + ... +（N - 1）= N（N - 1）/ 2

這是第n個第一個triangular number它是值得提交到內存。

給出的數字-n（n + 1）/ 2 - 似乎是不正確的，但它非常接近真實數字。我認爲他們假定循環會運行1 + 2 + 3 + ... + n次而不是0 + 1 + 2 + ... + n - 1次。

由此可以更容易地看出O（術語）的術語來自何處。注意n（n - 1）/ 2 = n，所以在我們掉落常數和低階項的大O陸地上，我們只剩下n 。