我知道这不是严格意义上的编程问题，但它是一个计算机科学的问题，所以我希望有人能帮助我。
我一直对我的算法功课，找出大哦，大欧米茄，西塔等，有多种算法。 我被发现他们的C和N 0值，证明他们和所有进展顺利。
但是，我遇到我在集最后两个问题，我努力搞清楚如何做他们（和谷歌是没有帮助很大）。
我还没有收到要弄清楚求和的大哦/欧米茄。
我的最后两个问题是：
和
我的问题是，如何证明？
例如，在第一个，直观地看不到I 2的该求和如何为O（N 3）。 第二个让我困惑，甚至更多。 有人能解释如何显示这些求和的大哦，和大欧米茄？
我的猜测是什么的问题语句的意思是，如果你总结了一些计算其运行时间是成比例的I 2在第一种情况下的结果，和比例登录2在第二种情况下我。 在这两种情况下，整体的总和的运行时间是“主导”，由N的较大值的总和中，因此两者的整体大O的评估将是N * O（F），其中f是函数你”再总结。
http://en.wikipedia.org/wiki/Big_O_notation
G（M）= O（F（米））将N次重复是O(N*f(m))对于任何F（N）。
我的总和=我的1..N * G（i）是O(N*f(N))如果g（N）= O（F（N））和f是单调的。
定义：G（N）= O（F（N））如果一些C，M存在，因此对所有的n>米， g(n)<=c*f(n)
的总和是对i = 1 ... N的i*f(i)
如果f是在我单调，这意味着每一个项是<= 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都是单调的。
Σ（i = 1到n）的I 2 = N（N + 1）（2N + 1）/ 6，其为O（n 3）。
需要注意的是（N！）2 =（1个N）（2（N-1））（3（N-2））...（（N-1）2）（N + 1）
=Π（i = 1到n）的I（N + 1-i）的
> =Π（I = 1到n）N
[例如，因为对于每个i = 1到n，第（i-1）（NI）> = 0与比较格雷厄姆/ Knuth的/ Patashnik ，第4.4节]
= N N。
因此，正！ > = N N / 2，所以
Σ（i = 1到n）的日志I =Π登录（i = 1到n）的I =日志N！ > =日志N N / 2 =（N / 2）日志N，其为Ω（N log n）的。
跳转出来给我的最简单的方法是通过感应一个证明。
对于第一个，基本上你需要证明
sum (i=1 to n) i^2 < k*n^3, k > 2,n > 0
如果我们使用感应的广义原理和取n = 1和k = 2的基础案例。
我们得到1<2*1 。
当然现在采取归纳假设，那么我们就知道
sum(i=1 to n) i^2<k *n^3 ，与位趣味数学的，我们得到
sum(i=1 to n) i^2+(n+1)^2 < k *n^3+(n+1)^2 。
现在表明k * n^3+(n+1)^2 < k *(n+1)^3
k *n^3+n^2+2n+1 < k *n^3+k *(3n^2+3n+1)
k *n^3 < k *n^3+(3k-1) *n^2+(3k-2) *n+k-1
因此，我们最初的结果是正确的。
对于第二个证明你需要证明sum(i=1 to n) log_2(i) >= k*n*log(n)我将离开作为一个读者练习）。
主要步骤，虽然是sum(i=1 to n) log_2(i)+log_2(n+1)>=k*n*log(n)+k*log(n+1)对于某个k，所以清楚地k为1。
也许，你的CPU将成倍增加在固定时间内的32位整数。 但大哦，不关心“不到四十亿”，所以也许你要看看乘算法？
据钨 ，“传统的”乘法算法是O（n 2）。 作为n在这种情况下的位数，从而真正的log（n）的实际数量。 所以，我应该能够广场整数的时间为O 1..1（n.log（N））。 求和是O（日志（N 2）），这显然是O（的log（n）），用于O-的整体复杂性（n.log（N））。
所以，我很能理解你的困惑。
