2

以下是我在采访街网站上看到的 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) ;
}

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

4

1 回答 1

2

我会尝试一下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

量子点

于 2012-05-09T19:57:19.953 回答