有人可以解释Big-Oh如何与Summations结合使用吗? [英] Can someone explain how Big-Oh works with Summations?

问题描述

我知道这并不是严格意义上的编程问题，但是它是计算机科学问题，因此我希望有人可以帮助我.

I know this isn't strictly a programming question, but it is a computer science question so I'm hoping someone can help me.

我一直在做我的算法作业，并弄清了几种算法的Big-Oh，Big-Omega，Theta等.我通过找到它们的C和N ₀ 值来证明它们，一切都很好.

I've been working on my Algorithms homework and figuring out the Big-Oh, Big-Omega, Theta, etc, of several algorithms. I'm proving them by finding their C and N₀ values and all is going well.

但是，我遇到了集合中的最后两个问题，我正在努力弄清楚该怎么做(而Google并没有太大帮助).

However, I've come across my last two problems in the set and I'm struggling figuring out how to do them (and google isn't helping much).

我以前不必弄清楚Big-Oh/Omega的总和.

I haven't had to figure out the Big-Oh/Omega of summations before.

我的最后两个问题是:

• 显示i ² 的Σ(i = 1至n)为O(N ³ )

和

• 表明[log ₂ i] 的Σ(i = 1至n)为Ω(n log n)

我的问题是，我该怎么显示?

My question is, How do I show that?

例如，在第一个例子中，直觉上我看不到i ² 的总和是O(N ³ ).第二个让我更加困惑.有人可以解释如何显示这些总结中的Big-Oh和Big-Omega吗?

For example, in the first one, intuitively I can't see how that summation of i² is O(N³). The second one confuses me even more. Can someone explain how to show the Big-Oh and and Big-Omega of these summations?

推荐答案

最简单的方法是归纳证明.

The simplest approach that jumps out to me is a proof by induction.

对于第一个，本质上您需要证明这一点

For the first one, essentially you need to show that

sum (i=1 to n) i^2 < k*n^3, k > 2,n > 0

如果我们使用归纳的广义原理，并采用n = 1和k = 2的基本情况.

If we use the generalized principle of induction and take a base case of n=1 and k=2.

我们得到1<2*1.

现在当然采用归纳假设，那么我们知道

Now of course take the inductive hypothesis, then we know that

sum(i=1 to n) i^2<k *n^3，通过一些有趣的数学运算，我们可以了解

sum(i=1 to n) i^2<k *n^3, with a bit of fun math we get to

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

因此，我们的原始结果是正确的.

Therefore, our original result is correct.

对于第二个证明，您需要证明 sum(i=1 to n) log_2(i) >= k*n*log(n)，我将留给读者练习；).

For the second proof you need to show that sum(i=1 to n) log_2(i) >= k*n*log(n), which I'll leave as an exercise for the reader ;).

主要步骤是sum(i=1 to n) log_2(i)+log_2(n+1)>=k*n*log(n)+k*log(n+1)，对于k来说，显然k是1.

The main step though is sum(i=1 to n) log_2(i)+log_2(n+1)>=k*n*log(n)+k*log(n+1), for some k, so clearly k is 1.

这篇关于有人可以解释Big-Oh如何与Summations结合使用吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！