计算复杂度？

Question

我一直在尝试计算以下函数的复杂度：

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);

具体来说，while循环的复杂度。我被告知g(N)的复杂度是O(n)，但我不确定它的复杂度是多少，以及我如何计算它。我逐渐意识到复杂度不会是O(0.5n^2)，但不确定如何计算它，因为每次都减半。有人有什么想法吗？

Answer 1

如果g(n)是O(n)，那么复杂度是O(n*log(n))

为了进一步解释，让我们暂时忽略g(n)

k = n;
while(k > 0) {
    k = k / 2;
}

假设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)

log(1000) = 9.96注意，它只用了10次迭代就把k降低到零。这是log(n)计算复杂度的一个例子。

然后，当您在循环中添加g(n)时，这意味着您为每次迭代添加O(n)，这给出了总的O(n*log(n))。

Answer 2

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，其中[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(的复杂度。

Answer 3

你的算法的复杂度是：

您的第一个循环运行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))})