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の形式の項を取得します。

これを2つの別々の合計（1つは基数16、もう1つは基数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/1516n ⁺ 8/7 ⁸ⁿ -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

すべてのu..のおかげで私が探していた最終的な式は（あなたの作品に基づいて）：

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

これにより、アルゴリズムを実行するプログラムと同じ結果が得られます

Answer 4

シリーズが収束していないように見えます...つまり、合計は無限大です。数式が間違っているか、質問が間違っている可能性があります。