算法時間複雜度：i/= 2在循環中

int fun(int n) { 
    int count = 0; 
    for (int i = n; i > 0; i /= 2) 
     for (int j = 0; j < i; j++) 
      count += 1; 
    return count; 
}

我是一個非常新的時間複雜性計算。對於這個算法，我得到的答案是O（nlogn），但答案顯然是O（n）。算法時間複雜度：i/= 2在循環中

我的邏輯是外環有一個指數下降，並會發生log_base2_（N）次。內循環將總共運行N次，因爲它變成了幾何和（第一次迭代是N/2次，然後是N/4，然後是N/8 ...）。如果我把它們放在一起並且由於嵌套循環而使它們相乘，那就是我用O（NlogN）提出來的地方。我錯過了一些明顯的東西嗎？

來源

2017-09-13 user6142489

外循環將運行總共log（n）次。現在，如果你看到它第一次運行n次，接下來的N/2次等等，所以使得該系列

n(1 + 1/2 + 1/4 + 1/8 + 1/16 + ...)

這個總和將（2 * N）內循環，這意味着它是O（n）

因此時間複雜度是O（n），因爲外部循環運行O（logn）次並且內部循環運行O（n）次。

這不是O（nlogn）由於內環路不採取n步時，都實際上採取的所有步驟的總和將是O（n）的

來源

2017-09-13 11:03:03 marvel308

這是有幫助的。我認爲我把操作的總數與運行時間混淆了。如果我正確理解你的觀點，時間複雜性將是兩個循環中的更糟糕的情況，在這種情況下是O（n）。 – user6142489

@ user6142489通常，它不是兩個循環中最差的，而是最內層循環的總迭代次數。因此，正如在這個答案中指出的那樣，我們需要執行給出O（n）的總和的相應總和。然而請注意，通常的過程是採用每個循環的複雜性（因此不是_max_）的_product_，但是這會導致一個太鬆的界限，因爲最內層循環的迭代次數取決於當前的_一世_。 – qwertyman

有趣。謝謝。 – user6142489

算法時間複雜度：i/= 2在循環中

回答

相關問題