我有以下递归公式:
f(0) = 0
f(1) = 1
f(n) = n + f(floor(n/2))
可以用代码表示为:
int f(int n) {
int s = 0;
for (; n; n >>= 1)
s += n;
return s;
}
是否有一种封闭形式可以让我f(n)
一步计算?
如果没有,我还能做些什么来f(n)
更快地计算吗?
我有以下递归公式:
f(0) = 0
f(1) = 1
f(n) = n + f(floor(n/2))
可以用代码表示为:
int f(int n) {
int s = 0;
for (; n; n >>= 1)
s += n;
return s;
}
是否有一种封闭形式可以让我f(n)
一步计算?
如果没有,我还能做些什么来f(n)
更快地计算吗?
在OEIS上搜索给出了这个系列:
A005187: a(n) = a([n/2]) + n; 1/sqrt(1-x) 展开的分母也是 2^a(n);还有 2n - 2n 的二进制扩展中 1 的数量。
所以第二部分给出了 的公式2*n - bitcount(2*n)
。您可以使用一些有效的位计数实现来计算它,例如 gcc 的__builtin_popcount
.
还要注意 bitcount(2n) = bitcount(n)
推导如下:
让 n = sum(b[j] 2^j) for j=0...N
假设 b[N] = 1。定义
(a) F(n) = n + F(n/2) = n+n/2+n/4+... = 2 * n - (1/2 + 1/4 + ... 1/2 ^N) 按几何级数
这个函数 F 是一个实值函数。现在对于设置的每个位 b[j],floor 函数减去 b[j](sum(1/2^k, k=1...j+1))。这是因为它实际上取出了 1/2,但是随着它的传播,随后的术语被添加了。
所以
(b) f(n) = floor(F(n)-sum(b[j] sum(1/2^k, k=1...j+1),对于 j=0...N-1 )
将 (a) 代入 (b) 给出
(c) f(n) = floor(2n - (1/2 + 1/4 + ... 1/2^(N+1)) - sum (b[j] (sum(1/2^(k ), 对于 k=1..j+1), 对于 j=0...N-1))
好的,这部分很酷!观察当 b[j] 为 1 时,如果从粗体表达式中偷偷 1/2^(j+1) 到斜体的 sum 中,sum 里面的 sum 变成 1,这意味着
b[j] (sum(1/2^(k), for k=1..j+1), for j=0...N-1) = sum(b[j], for j=0. ..N-1)
所以方程(c)简化为
f(n) = floor(2*n - sum(b[j], for j=0...N-1) - remainder)
f(n) = 2*n - bitcount(n-2^N) - 1 ; because remainder >0 and <1
f(n) = 2*n - bitcount(n) ; b[N]=1, so bitcount(n)=bitcount(n-2^N)+1
其中余数是 sum(1/2^j, j=1,..N+1 and b[j-1]==0),但这个总和总是 >0 且 < 1(最多为 1-1 /2^(N+2) 和至少 1/2^(N+1),所以它可以作为 -1 移出地板。
还要注意 bitcount 运行时间可以等于设置的位数(http://gurmeet.net/puzzles/fast-bit-counting-routines/)。一些处理器将其作为单独的指令。
不确定乳胶是否在这里有效,但没有数学符号会很痛苦。我一直不得不编辑它,因为看起来总是有问题。
The function grows as follows -
f(n) = n + f(n/2)
f(n/2) can be further simplified as -
n/2 + f(n/4)
If we keep doing this, we will see n + n/2 + n/4 + n/8.....upto log n terms
= n (1 + 1/2 + 1/4 + 1/8...log n terms)
= n[ (1- (1/2)^log n)/(1/2)]
= 2n [1 - (1/2)^log n]
The term (1/2)^log n will become smaller and smaller as n increases, therefore the 2n term dominates. Hence f(n) belongs to big Theta (n)