总和[(i + 1) (n - i), {i, 0, n - 1}]
这是 (i+1)(n-1) 的总和，边界从 i=0 到 n-1。
是 O(n^2) 还是 O(n^3)？你能解释一下你是怎么找到它的吗？谢谢。
问问题
286 次
3 回答
4
展开并使用 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）。
于 2010-12-08T01:48:09.383 回答
2
如果您正在谈论评估总和所需的时间，那么它是 O(1) （因为它可以简化为封闭式公式）。如果你在谈论公式本身，然后将其展开并代入幂和，你会看到 n^3 的系数（最高阶）不为 0。
无论如何，O(n^2) 是 O(n^3) 的子集，所以...当问是 O(n^2) 还是 O(n^3) 时，一个简单的答案是 O(n ^3) （如果您知道答案永远不会是“两者都不是”）。
于 2010-12-08T01:51:51.357 回答
2
Wolfram|Alpha 午餐吃这些：
http://www.wolframalpha.com/input/?i=Sum%5B(i+%2B+1)+(n+-+i),+%7Bi,+0,+n+-+1%7D%5D
于 2010-12-08T02:43:36.287 回答