已解決430363個問題，去搜搜看，總會有你想問的

嵌套循環的時間復雜度

關注

首頁猿問嵌套循環的時間復雜度

源碼算法與數據結構

婷婷同學_ 2019-07-20 14:27:10

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

查看完整描述

3 回答

動漫人物

TA貢獻1815條經驗獲得超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)。

反對回復 2019-07-20

智慧大石

TA貢獻1946條經驗獲得超3個贊

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

反對回復 2019-07-20

關注

舉報

0/150

提交

取消