確定和分析這些不同循環的大O運行時間

Question

這裏是簡單的代碼，我想知道代碼的時間複雜度 我已經對它做了分析，我的老師告訴我說有一個錯誤在裏面。我無法弄清楚我錯在哪裏。需要幫助。感謝

j = 2 
while(j<n) 
{ 
    k=j 
    while(k < n) 
    { 
     sum + = a[k]*b[k] 
     k = k*k 
    } 
    k = log(n) 
    j += log(k) 
} 

在這裏我得到了答案

時間複雜度= O（N/loglogn）。

我只是想知道我錯了，

Answer 1

你從2去n，加入log log n蓄能器的每一步，所以你確實有n/log log n步驟。

但是，每步都做了什麼？每一步，你從j到n，累加器本身乘以每一步。那有多少個操作？ 我不是100％肯定，但基於搞亂了一下和this answer，這似乎最終是log log (n - j)步驟，或簡稱log log n。

因此，n/log log n步驟，做log log n操作的每一步，給你一個O(n/log log n * log log n)或O(n)算法。

---

一些實驗似乎或多或少的證實了這一點（蟒蛇），雖然n_ops似乎標誌位爲n變得更大：

import math 

def doit(n): 
    n_ops = 0 

    j = 2 
    while j < n: 
     k = j 
     while k < n: 
      # sum + = a[k]*b[k] 
      k = k*k 
      n_ops += 1 

     k = math.log(n, 2) 
     j += math.log(k, 2) 
     n_ops += 1 

    return n_ops 

結果：

>>> doit(100) 
76 
>>> doit(1000) 
614 
>>> doit(10000) 
5389 
>>> doit(100000) 
49418 
>>> doit(1000000) 
463527 

Answer 2

好。讓我們來看看。該

k=j 
while(k < n) 
{ 
    sum + = a[k]*b[k] 
    k = k*k 
} 

位採用什麼需要J（1）（2^I）達到ñ。即什麼2^i需要達到log_j（n）這是log_2（log_j（n））。現在你有

j = 2 
while(j<n) 
{ 
    // stuff that takes log_2(log_j(n)) 
    j += log(log(n)) 
} 

這將需要n/log(log(n))的步驟，但這些步驟需要不同的時間。如果他們平等的時間，你會是對的。但相反，你必須從{2焦耳到N /日誌（日誌（N））}總和log_2（log_j（N）），這是

sum for {j from 2 to n/log(log(n))} [log_2(log(n)) - log_2(log(j))] 

這不是那麼簡單。至少，我想我已經指出了你可能錯誤的地方，這是個問題。