設 n 為 2 的冪。
int sum = 0;
for (int i = 1; i < n; i *= 2)
for (int j = 0; j < n; j )
sum = 1
時間復雜度是 O(N) 還是 O(nlogn)。謝謝！
uj5u.com熱心網友回復：
所以首先，沒有必要知道 n 是什么型別的數字，因為漸近復雜度取決于任何任意 n（只要它是一個正整數）。
我們還知道內回圈將進行 n 次迭代，因此我們可以將內回圈的時間復雜度表示為O(n)。
關于外回圈。我們知道，在每次迭代中，我們將 的值加倍i。由于i在初始化時不為零，因此肯定會通過加倍來增加。由于我們實際上i在每次迭代中加倍，我們知道我們以指數級遞增的迭代步長（對于 i=1、2、4、8、16、32、64、128...）達到 n。因此，當我們越來越接近它時，達到 n 的步數會越來越小。現在知道了這一點，我們看到我們最多進行 log(n) 次迭代以達到 n。
為什么？-> 這在數學上可能是非正式的，但我希望這沒問題。為了計算迭代次數，必須求解這個方程：2^x = n，其中 x 是迭代次數。通過上面的解釋，我們基本上可以看出這一點。在每個迭代步驟中，我們將 i 加倍，直到達到 n。x 的解是： x < log_2(n)
因此外回圈的時間復雜度為O(log(n))。
知道這一點，可以簡單地將復雜性乘以O(log(n)n)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/434650.html
上一篇：如何使用SED洗掉從第一個模式開始的文本，直到第二次出現結束模式？
下一篇：對稱一維陣列Python