math - この式は O(n^2) ですか、それとも O(n^3) ですか?

Question

Sum[(i + 1) (n - i), {i, 0, n - 1}]

これは、i=0 から n-1 までの境界を持つ ( i+1)(n-1) の合計です。

それはO（n ^ 2）またはO（n ^ 3）ですか？どうやってそれを見つけたのか説明してもらえますか？ありがとう。

Answer 1

sum(i^k) の閉じた形式の式を展開して使用します。つまり、

(i + 1)(n - i) = n * i - i * i + n - i

となることによって

sum[(i + 1)(n - i)] = sum(n * i) - sum(i * i) + sum(n) - sum(i)
                    = n * sum(i) - sum(i * i) + n * n - sum(i)
                    = (details elided)
                    = O(n^3).

「詳細は省略」のステップで、各合計を閉形式の式に展開し、 の係数がn^3ゼロではないことに注意してください (それは です1 / 6)。

Answer 2

合計を評価するのに必要な時間について話している場合、それは O(1) です (閉じた形式の式に減らすことができるため)。式自体について話している場合は、それを展開して累乗和を代入すると、n^3 の係数 (最高次数) が 0 ではないことがわかります。

とにかく、O(n^2) は O(n^3) のサブセットなので... O(n^2) か O(n^3) かを尋ねると、簡単な答えは O(n ^3) (答えが「どちらでもない」とわかっている場合)。

Answer 3

Wolfram|Alphaは昼食にこれらを食べます:

http://www.wolframalpha.com/input/?i=Sum%5B(i+%2B+1)+(n+-+i),+%7Bi,+0,+n+-+1%7D%5D