相关疑难解决方法(0)

我在想..从n个元素开始的算法的复杂性是什么(我通过做任何事情来运行).我取下一个元素,我再做一次.我取下另一个元素再做一次,直到我只剩下一个元素.是O(n log n)？我无法想象它......

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

我一直在研究我的算法作业,并找出几种算法的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吗？

如果我必须添加任意数字，例如数字 1,12,14,71,83,21... 那么此操作的时间复杂度是多少？

我知道两个数字相加的时间复杂度为 O(1)，但是 n 个数字的列表又如何呢？假设我为此目的使用最好的数据结构来存储它们，如果有的话，这会对过程产生任何影响！

提前致谢！