algorithm - 系列求和计算算法复杂度

Question

我有一个算法，我需要计算它的复杂度。我接近答案但我有一个小数学问题：该系列的求和公式是什么

½(n ⁴ +n ³ ) 其中 n 的模式是 1, 2, 4, 8, ... 所以级数变为：

½(1 ⁴ +1 ³ ) + ½(2 ⁴ +2 ³ ) + ½(4 ⁴ +4 ³ ) + ½(8 ⁴ +8 ³ ) + ...

Answer 1

对于 k=0,1,2...，将 n 表示为 2^k 可能会有所帮助

将其代入原始公式以获得 (16^k + 8^k)/2 形式的项。

您可以将其分解为两个单独的总和（一个以 16 为底，一个以 8 为底），每一个都是几何级数。

S1 = 1/2(16^0 + 16^1 + 16^2 + ...)

S2 = 1/2(8^0 + 8^1 + 8^2 + ...)

几何级数的第 J 个部分和是 a(1-r^J)/(1-r) 其中 a 是初始值，r 是连续项之间的比率。对于 S1，a=1/2，r=16。对于 S2，a=1/2，r=8。

乘以它，相信你会发现前J项之和为O(16^J)。

Answer 2

你问的是

½Ʃ ((2 ^r ) ⁴ +(2 ^r ) ³ ) 从 r=1 到 n

（对不起，丑陋的数学；这里没有 LaTeX。）

结果是 16/15 16 ⁿ + 8/7 8 ⁿ - 232/105

请参阅http://www.wolframalpha.com/input/?i=sum+%282%5Er%29%5E4%2B%282%5Er%29%5E3+from+r%3D1+to+n。

您不需要确切的公式。您只需要知道这是一个 O(16 ⁿ ) 算法。

Answer 3

感谢你们所有人……我正在寻找的最终公式（基于您的作品）是：

((1/15 2^(4(log2(n)+1))  +  8^(log2(n)+1)/7  -232/105)/2) + 1

这将给出与运行算法的程序相同的结果

Answer 4

看起来你的系列不收敛......也就是说，总和是无穷大的。也许你的公式是错误的，或者你问错了问题。