c++ - 在 O(logn) 中从 0 ~ N 计数

Question

以下是我在interview street网站上看​​到的C++代码，从0~a(输入数字)开始计算1的位，我们可以说是1~a，因为0没有1。此代码的时间复杂度为 O(logn)，使用递归。

我只是不明白其中的逻辑。谁能解释为什么？谢谢!

long long solve(int a)
{
 if(a == 0) return 0 ;
 if(a % 2 == 0) return solve(a - 1) + __builtin_popcount(a) ;
 return ((long long)a + 1) / 2 + 2 * solve(a / 2) ;
}

顺便说一句，__builtin_popcount() 是 GNU 提供的一种内置方法，用于计算为 1 的位。

Answer 1

我将尝试一下 O(lg n) 的复杂性。请注意，虽然证明应该仍然适用于运行时间，但我不太了解该函数的作用。

鉴于我们的递归关系:

T(a) = 0, if a == 0
     | T(a - 1) + O(1), if a is divisible by 2
     \ O(1) + T(a/2)

我将在这里使用迭代方法:

T(a) = T(a/2) + O(1)
T(a) = T(a/2^2)) + O(1) + O(1)
T(a) = T(a/2^k)) + (k-1)O(1)
// continue unrolling until we reach the base case
T(a) = 0 + O(1) + ... + O(1) + O(1) = kO(1)
// k here corresponds to lg a since we continued dividing the problem set in half
T(a) = (lg a)*O(1)
T(a) = lg a

Q.E.D.