首頁猿問嵌套循環(huán)的時間復(fù)雜度

嵌套循環(huán)的時間復(fù)雜度

源碼算法與數(shù)據(jù)結(jié)構(gòu)

婷婷同學(xué)_ 2019-07-20 14:27:10

嵌套循環(huán)的時間復(fù)雜度我需要計算以下代碼的時間復(fù)雜度：for (i = 1; i <= n; i++) { for(j = 1; j <= i; j++) { // Some code } }是嗎O(n^2)?

查看完整描述

3 回答

動漫人物

TA貢獻1815條經(jīng)驗獲得超10個贊

解釋這一點的一個快速方法是將其形象化。

如果i和j都是0到N，則很容易看到O(N^2)。

O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O

在這種情況下，它是：

O
O O
O O O
O O O O
O O O O O
O O O O O O
O O O O O O O
O O O O O O O O

這是N^2的1/2，仍然是O(N^2)。

反對回復(fù) 2019-07-20

智慧大石

TA貢獻1946條經(jīng)驗獲得超3個贊

實際上，它是O(n^2)。

反對回復(fù) 2019-07-20

關(guān)注

舉報

0/150

提交

取消

購課補貼
聯(lián)系客服咨詢優(yōu)惠詳情

慕課網(wǎng)APP
您的移動學(xué)習(xí)伙伴

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號