需要解釋算法的時間複雜性解決方案

Question

我的軟件工程類介紹剛剛達到時間複雜度並學習如何分析某些算法。我很難看到他們如何得到解決方案，並希望有人能夠解釋它，希望有一些合理的證據？

void foo(int N) { 
    int k = 1; 
    while (k < N * N) { 
     k = k * 2; 
    } 
} 

他們的解決方案是，這個功能的大澳是O（logN）的 [我明白這裏提到日誌基地2]

我試圖通過思考來解決這個多少次會通過將隨機值分配給N進行迭代，我無法找到模式，有什麼幫助？

Answer 1

k每次增加因子2的事實是使得算法logN的原因。實際上，它是log(N^2)，但使用對數屬性我們可以將其簡化爲2log(N)，然後通過將極限作爲N接近無窮大以獲得log(N)來刪除2。

因此，時間複雜度爲O(logN)。

編輯：此外，可以看出，k開始於1和程序結束時k大於或等於N * N。如果我們採用log(N^2)，我們將知道程序將運行多少次迭代。在這樣做的情況下，我們也可以通過獲取log(N^2)的上限來確定k的結束值。

編輯：一個例子是N = 10：N的正方形是100。因此，k將增加，直到兩個以上的冪或等於100，即128。

Answer 2

使用你的高中代數。在p迭代之後，k的值是2^p。 （這很容易檢查。）當k >= N^2時，循環將停止執行。代替，循環停止時

2^p >= N^2 

現在解決：

log_2(2^p) >= log(N^2) 
p >= 2 log(N) 

所以循環將在非常接近2 log(N)迭代停止。這是O（log（N））。

只有在操作數大小存在固定限制的情況下，您可能需要指出乘法是恆定時間才能完成任務。沒有這樣的限制，問題也取決於乘法的漸近行爲。

順便說一下，O（log N）對於所有對數底數都是相同的。 base只是通過一個常數來改變日誌的值，big-O忽略了常量因素。