3

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

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)，但我不确定如何计算它，因为每次减半。有人有想法么？

4

3 回答 3

4

如果 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))

于 2013-01-16T22:26:32.467 回答
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 n]，，其中[y]是 的整数部分y。您始终可以表示[log n]为 a 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-17T20:43:42.277 回答
0

您的算法的复杂性是：

您的第一个循环运行 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-22T10:59:02.887 回答