什麼是嵌套循環的大O，其中外環是n^2

for(int i = 1; i < n **2; i++) 
{  
    for(int j = 1; j < i; j++)  
    { 
    s = s;  
    } 
}

由於outter循環的大O爲O（n^2），它仍然會乘以內循環總大O符號爲n（n^2） - > O（n^3）？什麼是嵌套循環的大O，其中外環是n^2

如果將內部循環條件更改爲'j user2023861

在外部循環中，我可以取值從1到n^2。然後對於每個值，內部循環從1到i。對i = 1執行的操作次數是1，i = 2是2，...，i = n^2是n^2。

因此，操作總數是i從1到n^2的總和。這是一個衆所周知的series，它具有（n^2）（n^2 + 1）/ 2的閉合形式，即O（n^4）

2015-09-28 18:42:24

好吧，讓我跟進，直到你把這兩個函數乘以一起除以二。爲什麼在這種情況下你除以二？ – ryandonohue

@ryandonohue Chad將所有數字從1到n^2相加。對這樣的數字求和的公式是n（n + 1）/ 2。 https://cseweb.ucsd.edu/groups/tatami/kumo/exs/sum/這就是「二分」來自哪裏。 – user2023861

我編輯了一個包含相關係列的鏈接，但你也可以自己想想。如果你將系列的前半部分（1,2,3，...）添加到後半部分（n^2，n^2-1，n^2-2，...），那麼你（n^2/2）（n^2 + 1），這是另一種寫作方式（n^2）（n^2 + 1）/ 2 –

回答