該算法的大O運行時間

Question

我發現很難分析算法的時間複雜度。以此算法爲例，我如何在O表示法中找到運行時間？

loop(n) 
i = 1 
while i ≤ n 
    j = 1 
    while j ≤ i 
     j = 2 ∗ j 
    i = i + 1 

Answer 1

從你的文章我明白，你知道O符號的含義，但有一些應用它的問題。在這個簡單的例子中，確定循環執行的次數（取決於您的輸入大小）就足夠了。爲了獲得最終的價值，你必須把它結合起來。

第一步：分析每個循環的執行次數。 （非環或遞歸語句具有O（1）。）

while(i<=n) 
... 
i=i+1 

被執行n次，從而爲O（n）

內環 而（j < = I） 當J = J * 2

執行了i/2次，但我受外部循環限制了n。所以這是O（n）。

由於有在外環是內環與O（N）必須乘以asymptitics，即N * N =>爲O（n^2）

Answer 2

當給這樣的代碼，它通常有助於從內到外的工作。你的內循環在這裏給出：

j = 1 
While j <= i 
    j = 2 * j 

這個循環的工作原理是反覆加倍j直到它大於i。在超過i之前，您可以加倍1的次數是Θ（log i），所以每次運行內循環時，它都會運行Θ（log i）。

外環從1計數至n，所做的工作是

日誌1 +日誌2 + ... +日誌N

=日誌（1 * 2 * .. * n）（使用對數屬性）。

=的log（n！）

= Θ（N log n）的。

最後一步從Stirling's approximation開始。

因此總的來說，時間複雜度爲Θ（n log n）。