这个表达式是 O(n^2) 还是 O(n^3)？

发布于 2024-10-06 17:09:28 字数 131 浏览 11 评论 0原文

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

是 ( i+1)(n-1) 的总和，范围从 i=0 到 n-1。

是 O(n^2) 还是 O(n^3)？你能解释一下你是如何找到它的吗？谢谢。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

深爱成瘾 2024-10-13 17:09:28

展开并使用 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< /代码>）。

Expand and use the closed-form expressions for sum(i^k). To wit,

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

so that

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).

In the step "details elided", expand each sum to its closed-form expression and note that the coefficient of n^3 is not zero (it's 1 / 6).

回复收藏 0 原文