algorithm - 如何计算 for (int i = n - 1; i != 0; i/= 2) 的时间复杂度？

Question

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 为负数时我没能得到

Answer 1

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

当 n - 1 是 2 的幂时，所以 n - 1 == 2**a 对于某些 a，则循环将执行 a + 1 次(一次 for 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) 之间的差距由 some 有限常数从上面限制，那么它就没有区别。出于同样的原因，您不必担心对数的底数(2、10 或 e，它只是一个常数因子)，甚至不必担心循环是否执行了 lg(n - 1) 次或 lg( n - 1 +(-) m) +(-) p 次对于任何常数 m 和 p。