算法 - VoidCC

的時間複雜度計算什麼是以下程序的複雜性：算法

void function(int n) 
{ 
int i, j, k , count =0; 
for(i=n/2; i<=n; i++) 
    for(j=1; j=j + n/2<=n; j++) 
     for(k=1; k<=n; k= k * 2) 
     count++; 
}

現在按照我的理解外循環執行N/2次。內循環執行n/2次，第三個內循環執行記錄n次。現在，如果我們將算法的時間複雜度表示爲函數T（n）。

T（N）= N/2 * N/2 *日誌N = N^2/4 *日誌N

現在對於n個項log n中也非常大的輸入大小與術語n^2相比較小。所以根據我的理解，算法的時間複雜度必須是O（n^2）。但我已經檢查了這個程序的答案，它說答案是O（n^2logn）。

任何人都可以幫助我理解爲什麼我們不能忽視n值較大的術語log n嗎？或者我的計算錯了？

來源

2014-11-22 Beast

是，數（n）大於多項式較小，但是當它乘以它仍然是一個因素。 O（log（n））比O（n）慢，但O（nlogn）是一件事情，它和你所得到的相似。 O（nlogn）！= O（n）。一張圖可以很好地說明這一點。 – keyser 2014-11-22 17:38:15

感謝keyser。舉例來說，如果我們有時間複雜度T（n）= n^3 + n^2 + n那麼對於非常大的n值，我們忽略n^2和n這個詞，那麼爲什麼我們不能在這裏做同樣的事情？ – Beast 2014-11-22 17:41:16

是的，我們這樣做，因爲它們是分開的。漸近地，其他的不會有任何顯着的影響，但是漸近地說，O（nlogn）比O（n）增長得更快，因爲log（n）大於常數。我喜歡benji對他們如何被刪除的插圖。 – keyser 2014-11-22 17:42:23

您只能忽略常數值。如果n增加，log（n）也增加。

來源

2014-11-22 17:38:04 axiac

感謝axiac。但是舉例來說，如果我們有時間複雜度T（n）= n^3 + n^2 + n，那麼對於非常大的n值，我們忽略n^2和n這個詞，那麼爲什麼我們不能做同樣的事情這裏？ – Beast 2014-11-22 17:42:46

@Beast您可以忽略n^2和n，因爲您將它們添加到n^3不會像您的示例中那樣倍增。 – Everettss 2014-11-22 17:59:54

如果我們假設你的algorihtm得到了運行時間功能（不完全正確）：

T(n)=n/2*n/2*log n =n^2/4*log n= an^2*log(n)

你可以做形式漸近分析：

enter image description here

我們可以很容易證明我們可以找到c1和c2來滿足：

enter image description here

所以最後你可以說，你的算法已經得到了複雜性：

enter image description here

來源

2014-11-22 18:20:06 Everettss

算法

回答

相關問題