Skiena算法设计手册 - 几何系列澄清
从书中拍摄的照片.
这是对本书几何系列的解释,我不明白.恒定比率是a对的吗？所以让我们来看第一个词(只是和函数),for n = 5和constant ratio = 2.
所以我们会这样:
2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 = 1 + 2 + 4 + 8 + 16 + 32 = 63
不,如果我使用RHS,
a(a^n+1 - 1)/(a - 1).所以它会给出这个:2(2^5+1 - 1)/(2 - 1)因为n = 5这给了126.
他们怎么能平等？
后来它也说:' 当a> 1时,每个新术语的总和会迅速增长. '他是在谈论空间复杂性吗？
因为我没有得到big-theta符号.因此,对于n = 5和a = 2将采取大-θ(64),64(2的6次方)步骤是什么？
这是一些ruby代码:
n = 5
a = 2
sum = 0
for i in 0..n do
sum = sum + a**i
end
puts sum # prints 63
我可以看到n+1步骤.
有什么帮助理解这个吗？