以下代碼的時間複雜度如何爲O（n）？

我正在解決Interview Bit上的一個時間複雜問題，它在圖像中給出。以下代碼的時間複雜度如何爲O（n）？

這個問題的正確答案是O（N）。但根據我的觀點，答案應該是O（NlogN）。由於第一個「for循環」的複雜度應該是O（logN），因爲變量i在每次迭代中被除以2，並且我研究過每當循環變量乘以或除以2時，時間複雜度爲O （10即）。現在，對於第二個「for循環」，複雜度應該是O（N），因此，最終的複雜度應該是O（N * logN）。

任何人都可以請解釋我錯了嗎？

來源

2017-02-14 DG4

請注意，O（NlogN）實際上並不是_wrong_，因爲O（）是一個上限。它只比O（N）的信息量少。 – Gassa

出錯的地方在於，當外部循環輸入O（log N）次時，提供可能整個算法確實需要O（？* log N）的想法，內部循環不執行cN次的平均值一些常量c，用於外部循環的每次執行。正如IVlad的答案所述，你需要做數學導致幾何系列。 – moreON

做實際的數學：

T(N) = N + N/2 + N/4 + ... + 1 (log_2 N terms in the sum)

這是一個幾何級數具有比1/2，使之和等於：

T(N) = N*[1 - (1/2)^(log_2 N)]/(1 - 1/2) = 
    = [N - N/(2^log_2 N)]/0.5 = 
    2^log_2 N = N 
    = (N - 1)/0.5

所以T(N)爲O(N)。

來源

2017-02-14 10:20:38 IVlad

@IVIad，我明白你是如何計算T（n）= O（n）的。但我認爲你已經計算了僅用於外循環。但是我們應該爲內循環做些什麼？ – DG4

@ DG4不，它適用於整個程序。當'i = N'時，內部執行'N'次。當'i = N/2'時，內部執行'N/2'次，依此類推。所以總和考慮了一切。 – IVlad

以下代碼的時間複雜度如何爲O（n）？

回答

相關問題