O(n)的算法又如何也可以是O(n ^ 2)，O(n ^ 1000000)，O(2 ^ n)? [英] How can an algorithm that is O(n) also be O(n^2), O(n^1000000), O(2^n)?

问题描述

所以这个问题的答案有什么区别在Θ(n)和O(n)之间?

指出基本上，当我们说一个算法是O(n)时，它也是O(n ² )，O(n ^1000000 )，O(2 ⁿ )，...，但是Θ(n)算法不是Θ(n ² )."

states that "Basically when we say an algorithm is of O(n), it's also O(n²), O(n^1000000), O(2ⁿ), ... but a Θ(n) algorithm is not Θ(n²)."

我了解Big O代表上限或最坏情况，因为我不了解O(n)也是O(n ² )，其他情况比O(n)差

I understand Big O to represent upper bound or worst case with that I don't understand how O(n) is also O(n²) and the other cases worse than O(n).

也许我有一些基本的误解.我已经挣扎了一段时间，请帮助我理解这一点.

Perhaps I have some fundamental misunderstandings. Please help me understand this as I have been struggling for a while.

谢谢.

推荐答案

想一想big-Oh的含义是有帮助的:如果一个函数是O(n)，则c*n，其中c是一些正数，是上限.如果c*n是一个上限，则很明显，对于整数，c*n^2也将是一个上限.还有c*n^3，c*n^4，c*n^1000等

It's helpful to think of what big-Oh means: if a function is O(n), then c*n, where c is some positive number, is the upper-bound. If c*n is an upper-bound, it's clear that for integers, c*n^2 would also be an upper-bound. Also c*n^3, c*n^4, c*n^1000, etc.

下图显示了函数的增长，这些函数是函数右侧"的上限；也就是说，它在较小的n上增长更快.

The below graph shows the growth of functions, which are upper bounds of the function "to the right" of it; i.e., it grows faster on smaller n.

这篇关于O(n)的算法又如何也可以是O(n ^ 2)，O(n ^ 1000000)，O(2 ^ n)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！