有人可以解释Big-Oh如何与Summations一起使用？

Question

我知道这不是一个严格的编程问题,但它是一个计算机科学问题所以我希望有人可以帮助我.

我一直在研究我的算法作业,并找出几种算法的Big-Oh,Big-Omega,Theta等.我通过找到他们的C和N ₀值来证明他们并且一切顺利.

然而,我在集合中遇到了我的最后两个问题,我正在努力弄清楚如何做到这些(并且谷歌没有多大帮助).

我以前没有必要弄清楚Big-Oh/Omega的总结.

我的最后两个问题是:

• 证明i ^2的 Σ(i = 1到n)是O(N ³)

和

• 证明[log ₂ i]的Σ(i = 1到n)是Ω(n log n)

我的问题是,我该如何展示？

例如,在第一个中,直观地我看不出i ^2的总和是O(N ³).第二个让我更加困惑.有人可以解释如何展示这些总结的Big-Oh和Big-Omega吗？

Answer 1

http://en.wikipedia.org/wiki/Big_O_notation

O(N*f(m))对于任何 f(N)，g(m)=O(f(m)) 重复 N 次。

i*g(i) 的 i=1..N 之和是O(N*f(N))如果 g(n)=O(f(n)) 并且 f 是单调的。

定义：g(n)=O(f(n)) 如果存在一些 c,m，那么对于所有 n>m，g(n)<=c*f(n)

总和适用于 i=1..N 的情况i*f(i)。

如果 f 在 i 中是单调的，这意味着每一项都 <= i f(N) <= N f(N)。所以总和小于N*c*f(N)总和O(N*f(N))（由相同的 c,m 见证，使得 g(n)=O(f(n))）

当然，log_2(x) 和 x^2 都是单调的。