big-o - 什么是大 O 符号？你是如何想出像 O(n) 这样的数字的？

Question

这个问题在这里已经有了答案:




11 年前关闭。

Possible Duplicate:
Plain english explanation of Big O

我想这可能是类里面教的东西，但作为一个自学成才的程序员，我很少看到它。

我认为这与时间有关，O(1) 是最好的，而 O(n^n) 之类的东西非常糟糕，但有人可以指出我对它实际代表什么的基本解释，这些数字来自哪里？

Answer 1

Big O 指的是最坏情况下的运行时顺序。它用于显示算法根据数据集的大小(n-> 项目数)扩展的程度。

由于我们只关心顺序，常数乘数被忽略，任何比主项增长速度慢的项也被删除。一些例子:

单个操作或一组操作是 O(1)，因为它需要一些恒定的时间(不随数据集大小而变化)。

一个循环是 O(n)。循环遍历数据集中的每个元素。

嵌套循环是 O(n^2)。嵌套嵌套循环是 O(n^3) 及以后的。

二叉树搜索之类的东西是log(n)，比较难显示，但是在树的每一层，可能的解数减半，所以层数是log(n)(假设树是平衡的)。

像找到一组最接近给定值的数字之和之类的事情是 O(n!)，因为需要计算每个子集的总和。这真是太糟了。