計算複雜性？

我一直在試圖計算下列功能的複雜性：計算複雜性？

k=n; 
while(k>0) 
    g(n); 
    k=k/2; {Comment: this is integer division, so 1/2=0} 
end while; 
for(j=0;j<m;j++) 
    f(m);

具體來說，在同時loop.I的複雜性被告訴，G（N）的複雜度爲O（n），但我不確定它會是什麼複雜性，以及我會如何解決它。我已經認識到複雜性不會是O（0.5n^2），但我不確定如何計算它，因爲每次都減半。有人有主意嗎？

來源

2013-01-16 user1899174

如果您的問題大小減半每次迭代中，多少次迭代，你需要做的，達到0問題大小？即給定一個數字'n'，你需要在你的（整數）計算器上按/ 2多少次才能達到0？ –

@Karel我試過它的數字，如8，這給出了n/2，但一個數字，如20給n/4，所以我不確定。 – user1899174

該數字實際上稱爲對數（基數爲2，因爲您除以2）。即外循環是重複log（n）次，其餘的應該很容易:)另請參閱http://cs.stackexchange.com/questions/581/intuition-for-logarithmic-complexity –

如果G（N）是O（n），那麼你的複雜度爲O（n *的log（n））

爲了進一步說明，讓我們暫時忽略

克（N）

令說N = 1000

然後我們就會k的

Pass | k 
------------- 
0 | 1000 
1 | 500 
2 | 250 
3 | 125 
4 | 62 
5 | 31 
6 | 15 
7 | 7 
8 | 3 
9 | 1 
10 | 0 (stopped)

日誌（1000）= 9.96以下值注意它只需要10次迭代就可以將k降到零。這是一個log（n）計算複雜度的例子。

然後，當您添加循環內的G（N），這意味着你的每次迭代，這給了我們一個盛大的總氧量的增加O（N）（N *的log（n））

來源

2013-01-16 22:26:32

不一定，它也取決於f（m）的複雜性。 –

是的，但是如果f（m）的複雜度不大於O（n * log（n）），那麼，這並不重要。 –

儘管while循環確實是O（nlogn），但是更緊的界限是O（n）。（O（N）是O（NlogN）的一個子集，while循環實際上是Theta（N）'） – amit

的while循環的複雜性顯然是O(n log n)。有log n迭代，因爲在每次迭代結束時，k除以2.要獲得迭代次數，請將n表示爲2的冪，例如2^x。如果2^x=n, then x = log n。這就是爲什麼while循環的複雜性是O(n log n)。不要混淆，因爲n沒有2的冪，這意味着log n並不總是一個整數，你應該寫，而不是log n，[log n]，其中[y]是y的整數部分。您始終可以將[log n]表示爲c* log n，其中c是常數，不會改變算法的複雜性。因此，您不需要[]函數和O(n log n)是可以接受和正確的答案。

for循環的複雜性取決於f(m)的複雜性。如果O（f（m））是O(1)，則循環是O（m），但是如果O(f(m))是O(m)，則循環是O(m^2)。因爲f(m)也是算法的一部分，所以如果您想確定整個代碼的複雜性，您需要知道f(）的複雜性。

來源

2013-01-17 20:43:42 Milos

的您算法的複雜度：

你的第一個循環運行O（LOGN）次，每次迭代所要做的G（N）。因此它需要

O(sum{i from 0 to log(n)}{O(g(i))}).

第二個循環運行m次。這需要：

O(sum{j from 0 to m}{O(f(i))})

你的算法的總複雜是：

O(sum{i from 0 to log(n)}{O(g(i))}) + O(sum{j from 0 to m}{O(f(i))})

來源

2016-06-22 10:59:02 xenteros

計算複雜性？

回答

相關問題