例如，當查看此代碼時：
for (int i = 1; i < n; i*=2)
for (int j = 0; j < i; j =2)
{
// some contstant time operations
}
是不是很簡單，因為外回圈是 log 而內回圈是 n ，結合起來的結果是 nlogn 的 big(O) ？
uj5u.com熱心網友回復：
以下是對問題中示例的分析。為簡單起見，我將忽略2內部回圈中的增量并將其視為1，因為就復雜性而言，它并不重要 - 內部回圈是線性的，i并且常數因子2無關緊要。所以我們可以注意到，外部回圈正在產生is 的值，這些值是 的冪2，n即：
1, 2, 4, 8, ... , 2^(log2 n)
這些數字也是內部回圈中的“恒定時間操作”為 each 運行的數字i。所以我們要做的就是總結上面的系列。很容易看出這些是幾何級數：
2^0 2^1 2^2 ... 2^(log2 n)
它有一個眾所周知的解決方案：
（來自維基）
我們有a=1, r=2, 和... 好吧n_from_the_image =log n。我們這里對不同的變數有相同的名稱，所以這有點問題。
現在讓我們替換并得到總和等于
(1-2^((log2 n) 1) / (1 - 2) = (1 - 2*n) / (1-2) = 2n-1
這是線性O(n)復雜度。
uj5u.com熱心網友回復：
通常，我們將O時間復雜度視為執行最內層回圈的次數（這里我們假設最內層回圈由O(1)時間復雜度的陳述句組成）。
考慮你的例子。第一個回圈執行O(log N)次數，第二個最里面的回圈執行O(N)次數。如果某件事O(N)被執行了O(log N)幾次，那么是的，最終的時間復雜度就是它們的乘積：O(N log N).
通常，這適用于大多數嵌套回圈：您可以假設它們的大 O 時間復雜度是每個回圈的時間復雜度的乘積。
break但是，當您可以考慮該宣告時，此規則也有例外。如果回圈有提前爆發的可能，時間復雜度會有所不同。
看看我剛剛提出的這個例子：
for(int i = 1; i <= n; i) {
int x = i;
while(true) {
x = x/2;
if(x == 0) break;
}
}
好吧，最里面的回圈是O(infinity)，所以我們可以說總時間復雜度是O(N) * O(infinity) = O(infinity)嗎？不。在這種情況下，我們知道最里面的回圈總是會中斷O(log N)，給出總的O(N log N)時間復雜度。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/487809.html
上一篇：c中qsort的問題