4

for (int i = n - 1; i != 0; i /= 2) ++k;

我无法理解如何计算上述时间复杂度。当 n 为负时，我无法弄清楚它的行为。谁能帮我到那里。当 n 为正时，我尝试过。

Statement            Code      Time 
1a                  i=n-1       1 
1b                  i != 0    log2n+1
1c                  i = i/2   log2n
2                    ++k      log 2n
Total running time       3 log 2n+2

当我分析 n 为正的代码时，我得到了这些值。但是当 n 为负时我没有得到

4

1 回答 1

4

该算法属于 O(log(n))。最长的运行时间出现在abs(n - 1)2 的幂时，因为在所有其他情况下，由于截断，某些i /= 2步骤会导致i取值（其绝对值是）略小于。abs(i / 2)

什么时候n - 1是 2 的幂，所以n - 1 == 2**a对于一些a，那么循环将被执行a + 1多次（一次用于i取每个值1 = 2**0, 2 = 2**1, 4 = 2**2, ..., n - 1 = 2**a）。也就是说，循环将被执行 lg(n - 1) + 1 次。

我认为您的一些困惑源于您试图解释在循环内采取了多少步骤，但请记住，这些常数因素对于渐近运行时无关紧要。为了证明运行时间是（比如说）O（log（n）），您只需要证明“n 的实际运行时间”/ log（n）的限制，当 n 接近无穷大时，小于无穷大。如果循环的每次迭代都需要三步或四步，或者一千步，谁在乎呢？只要实际运行时间和 log(n) 之间的差距从上面被一些有限常数那么它没有区别。出于同样的原因，您无需担心对数的底数（2，或 10，或 e，它只是一个常数因子），甚至循环是否执行 lg(n - 1) 次或 lg(对于任何常数 m 和 p，n - 1 +(-) m) +(-) p 次。

于 2013-09-16T19:36:41.613 回答