我更喜欢尽可能少的正式定义和简单的数学。
当前回答
f(x) = k(x)g(x) k 与 a(如果 a = +∞,这意味着有 N 和 M 等数,以至于每个 x > N 的, < M 等数。
sin x = O(x) when x → 0. sin x = O(1) when x → +∞, x2 + x = O(x) when x → 0, x2 + x = O(x2) when x → +∞, ln(x) = o(x) = O(x) when x → +∞。
更多例子
其他回答
测量软件程序的速度非常困难,当我们尝试时,答案可以非常复杂,并且充满了例外和特殊案例,这是一个很大的问题,因为所有这些例外和特殊案例都令人沮丧和无助,当我们想比较两个不同的程序,以确定哪个是“最快”。
好事:
邪恶的:
和那可怕的:
大O只是一种方式来“表达”自己,以一种常见的方式,“运行我的代码需要多少时间/空间?”
因此,你可能明白“n2”是什么意思,但要更具体,玩你的想法,你有一个简单的,最简单的分类算法;泡沫分类。
我的名单
比较 1 和 6 是最大的? Ok 6 是正确的位置,前进! 比较 6 和 3, oh, 3 是更少的! 让我们移动, Ok 列表改变了,我们需要从现在开始!
為每個項目,你再看所有項目一次,為比較,這也是“n”,所以為每個項目,你看“n”時刻意味著n*n = n2
我希望这就像你想要的那样简单。
这是一个非常简单的解释,但我希望它涵盖了最重要的细节。
让我们说你的算法处理问题取决于某些“因素”,例如,让我们做它N和X。
根据 N 和 X,您的算法将需要一些操作,例如在 WORST 案例中,它是 3(N^2) + log(X) 操作。
由于Big-O不太关心恒定的因素(aka 3),你的算法的Big-O是O(N^2 + log(X))。它基本上翻译“你的算法需要最糟糕的案例规模的操作数量”。
大 O 描述一类功能。
它描述了大输入值的快速功能的增长方式。
对于一个特定的函数f,O(f)分解了所有函数g(n),您可以找到一个n0和一个恒定的c,以便与n>=n0的g(n)的所有值都低于或相当于c*f(n)。
在较少的数学词语中,O(f)是一组函数,即所有函数,从某些值 n0 向前,增长缓慢或像 f 一样快。
如果 f(n) = n 那么
g(n) = 3n 是 O(f) 。 因为恒定的因素不重要 h(n) = n+1000 是 O(f) 因为它可能比所有值小于 1000 但对于大 O 只有大输入物质。
然而,i(n) = n^2不在O(f)中,因为一个四方函数比一个线性函数增长得更快。
当我们有一个函数,如f(n) = n+3 和我们想知道图表看起来如何喜欢,当n接近无限时,我们只是放下所有的连续和较低的顺序术语,因为它们不在乎什么时候n变得大。
常规和较低的命令时间的简单落下,正是找到下方和上方的功能的过程。
根据定义,一个函数是另一个函数的下层或上层界限,如果您可以找到一个恒定的函数,以便为每个 n 的输出比原始函数更大(或较小)。
f(n) = n*C > f(n) = n+3
而且是的 C = 2 会这样做,因此我们的函数 f(n) = n 可以是我们函数 f(x) = x + 3 的顶部界限。
相同的下限:
f(n) = n*C < f(n) = n+3
C = 2 會這樣做
