在漸近分析中添加日誌

有問題我正在努力工作，非常感謝您的幫助！什麼是時間複雜度...在漸近分析中添加日誌

for (int j = 1 to n) { 
    k = j; 
    while (k < n) { 
     sum += a[k] * b[k]; 
     k += log n; 
    } 
}

外循環運行n次。我不確定如何在內部循環中處理k+= log n。我的想法是，它是O（n^2）。向k添加log（n）並不完全得到額外的n個循環，但我認爲它小於O（n * log n）。很明顯，這只是一個猜測，並且在弄清楚如何以數學方式顯示的任何幫助將不勝感激！

來源

2011-05-02 chrismanderson

多少次內部循環執行呢？ '小區（第（n-j）的/的log（n））'。從那裏工作。 – 2011-05-02 20:55:25

在這裏你可以把log(n)當作一個常數。

循環的每次迭代將執行恆定的工作量（sum+=...; k+=...），其次數等於n/log(n)。循環的迭代次數爲n。總的工作是n^2/log(n)。

你看到一堆作業，像這樣的任何時間：

---------------------b------------------------- 
|O(blah) + O(blah) + O(blah) + O(blah) + O(blah) 
|O(blah) + O(blah) + O(blah) + O(blah)  . 
a|O(blah) + O(blah) + O(blah)    . 
|O(blah) + O(blah)       . 
|O(blah)  .   .   .   .

這是a*b * O(blah) - 試想廣場（在這裏我把. S）。它是二維矩形（矩形的一半）的恆定分數，因此是O(a*b)。

在上述情況下，B = n，A = n/log(n)，和O（等等）= O(1)（從內環路）

來源

2011-05-02 20:55:54 ninjagecko

謝謝 - 一個跟進。所以n/log（n） - 你剛纔看到的就是這個，對吧？是否有任何其他的技巧或建議來辨別n/log（n），除了在數學上更好;）？我的問題總是在弄清楚如何將代碼翻譯成數學方程，而且我經常感到驚訝的是，關於這個事實在線上的幫助很少。 – chrismanderson 2011-05-02 21:38:08

對於循環而言，它是一個常量（即，如果你喜歡這樣想的話，你可以將它從總和中抽出）。如果它不是'log（n）'而是'log（j）'（出於某種奇怪的原因），那將會更加困難。我首先要逐筆寫下工作量，並試圖看到一種模式。你也可以模擬它來綁定它（「哦，在n和n^2之間的某個地方......」）。您可以遞歸地重寫它，並使用http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method – ninjagecko 2011-05-02 21:42:27

可以很容易地「只是貯槽向上」：

外循環有你說的n步驟。內部循環有(k-j)/log n步驟。

這是（大約）：

n 
--- 
\  (n-j)    n*n 
/ -------- = ... = --------- 
___ (log n)   2*log(n) 
j=1

所以，它在總O((n^2)/log(n))。

來源

2011-05-02 20:57:19 phimuemue

可以正式進行類似如下：

enter image description here

來源

2014-04-25 21:07:09

在漸近分析中添加日誌

回答

相關問題