什么是嵌套循環的Big-O，其中內循環中的迭代次數由外循環的當前迭代確定？以下嵌套循環的Big-O時間復雜度是多少：for(int i = 0; i < N; i++) {
for(int j = i + 1; j < N; j++)
{
System.out.println("i = " + i + " j = " + j);
}}它還是O（N ^ 2）嗎？
3 回答
藍山帝景
TA貢獻1843條經驗 獲得超7個贊
是?；叵胍幌麓?O的定義：O（F（N））由定義說，運行時間T（N） ≤ KF（n）的一些恒定?。在這種情況下，步數將是（n-1）+（n-2）+ ... + 0，其重新排列為0到n-1的和; 這是
T（n）=（n-1）（（n-1）+1）/ 2。
重新排列，你可以看到T（n）總是≤1/ 2（n2）; 根據定義，因此T（n）= O（n 2）。
慕斯王
TA貢獻1864條經驗 獲得超2個贊
如果忽略System.out.println，則為N平方。如果你假設它所花費的時間在它的輸出中是線性的（當然它可能不是），我懷疑你最終得到O（（N ^ 2）* log N）。
我提到這不是挑剔，但只是要指出你在解決復雜性時不僅需要考慮明顯的循環 - 你需要考慮你所稱的復雜性。
添加回答
舉報
0/150
提交
取消