簡單的時間複雜度O（nlogn）

我在回顧一些面試的大O表示法，並且遇到了這個問題。簡單的時間複雜度O（nlogn）

for i = 1 to n do: 
    j = i 
    while j < n do: 
    j = 2 * j

簡單吧？外循環提供了n個步驟。並且這些步驟中的每一個我們執行分配j=i的單個步驟O（1），然後從j = i步進while循環的log（n-j）或log（n-i）。我認爲時間複雜度是O（nlogn），但答案是O（n）。

這裏是答案：

的運行時間大約是以下之和：Σ 1 + 日誌（N/I），其中i從1到n，其是Θ（n）中。

現在它已經有一段時間了，所以我有點生疏。 log(n/i)從哪裏來？我知道log(n) - log(i) = log(n/i)但是我認爲我們記錄（n-i）不是log（n） - log（i）。時間複雜度不是O（nlogn）？我相信我錯過了一些簡單的東西，但我現在已經盯着這個小時了，現在我開始失去理智了。

來源：這裏是源這個問題Berkeley CS 170, Fall 2009, HW 1

編輯：經過考慮之後多一點是非常有意義的內部循環的時間複雜度是log（N/I）。導致每個內部循環運行n-i次，但是我將每個循環加倍。如果內部循環總是從0開始，我們有log（n），但是要考慮循環的數量，我們不必循環log（i）。 log（n） - log（i）是log（n/i）。

來源

2017-10-07 OLIVER.KOO

要添加到所提供的答案[見這裏]（HTTPS：//數學。stackexchange.com/questions/74412/how-to-show-sum-limits-i-1n-log-left-fracni-right-thetan）這個數字如何是O（n） – RSon1234

謝謝@ RSon1234這正是我所知尋找！ –

我認爲該日誌（N/I）來自內環

通知j = i

如何，這意味着當i = 2（可以說N = 10）

內環

while j < n do: 
    j = 2 * j

將只運行從j=2到10其中j multilplies本身由2（因此日誌）&曲所以內循環運行log base 2 n/i times

我通過代碼&它看起來像線性時間，因爲大多數時間內循環的只運行一次跑了簡單的I = 10 ickly超支n=10

的值。

示例：當i的值變得如此時，如果將它乘以2，則得到大於或等於n，則不會多次運行內部循環。

所以如果n = 10你在內環一個執行從i=n/2 (if i=10/2=5)開始則j與J = 5開始，獲得在一次循環與2 &內環條件while j < n do:失敗乘以本身。

編輯：這將是O(n.log(n))如果j的值開始與J = 0，每次&內環跑從i到n

來源

2017-10-07 05:00:41

謝謝Sujal。我知道'j = i'和log（n/i）來自你在answer.h中提到的內部循環和行爲數。如果每個內部循環運行n-i次，爲什麼它不應該是log（n-i）。即使我們有log（n/i），爲什麼運行時o（n）不是log（n/i） –

可以看到答案的最後部分，這段代碼對於每個j只運行一次執行，/2的初始值，只需拿一支筆和一張紙寫下n = 10的簡單執行過程，你會發現執行的總步驟大約是16，這與n = 10或多或少類似，如果它是O（n。 log（n））它將是10 * 3或30次執行。 –

簡單的時間複雜度O（nlogn）

回答

相關問題