计算复杂性？

我一直在试图计算下列功能的复杂性：计算复杂性？

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

计算复杂性？

回答

相关问题