我知道这不是一个严格的编程问题，而是一个计算机科学问题，所以我希望有人能帮助我。
我一直在做我的算法作业，并找出几种算法的 Big-Oh、Big-Omega、Theta 等。我通过找到它们的 C 和 N 0值来证明它们并且一切顺利。
然而，我遇到了我在系列中的最后两个问题，我正在努力弄清楚如何解决它们（谷歌并没有多大帮助）。
我以前不必弄清楚总和的大哦/欧米茄。
我的最后两个问题是：
和
我的问题是，我如何证明这一点？
例如，在第一个中，直觉上我看不出 i 2的总和是 O(N 3 )。第二个更让我困惑。有人可以解释如何显示这些总和的 Big-Oh 和 Big-Omega 吗？
我想到的最简单的方法是归纳证明。
对于第一个，基本上你需要证明
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。
http://en.wikipedia.org/wiki/Big_O_notation
O(N*f(m))对于任何 f(N) ，g(m)=O(f(m)) 的 N 次重复。
i=1..N 的 i*g(i) 之和是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 of i*f(i)。
如果 f 在 i 中是单调的，这意味着每一项都是 <= i f(N) <= N f(N)。所以总和小于N*c*f(N)所以总和是O(N*f(N))（由使 g(n)=O(f(n)) 相同的 c,m 见证）
当然，log_2(x) 和 x^2 都是单调的。
我的猜测是，问题陈述的意思是，如果你对某些计算的结果求和，在第一种情况下，运行时间与 i 2成正比，在第二种情况下与 log 2 i 成正比。在这两种情况下，总和的运行时间都由总和中较大的 N 值“支配”，因此两者的整体大 O 评估将是 N*O(f) 其中 f 是你的函数重新求和。
Σ (i=1 to 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。与Graham/Knuth比较/Patashnik，第 4.4 节]
= n n。
因此，n! >= n n/2，因此
Σ (i=1 to n) log i = log Π (i=1 to n) i = log n! >= log n n/2 = (n/2) log n，即 Ω(n log n)。
您的 CPU 可能会在恒定时间内乘以 32 位整数。但是big-Oh不关心“少于四十亿”，所以也许你必须看看乘法算法？
根据Wolfram的说法，“传统”乘法算法是 O(n 2 )。尽管在这种情况下n是位数，因此实际上是log(n)的实际数字。所以我应该能够在 O(n.log(n)) 时间内对整数 1..n 求平方。求和是 O(log(n 2 ))，这显然是 O(log(n))，对于 O(n.log(n)) 的整体复杂性。
所以我很能理解你的困惑。