algorithm - 小o表示法 - 算法




大O和小O符号的区别 (2)

Big-O很少,因为< 。 Big-O是一个包容性的上限,而little-o是一个严格的上限。

例如,函数f(n) = 3n是:

  • O(n²)o(n²)O(n)
  • 不在O(lg n)o(lg n)o(n)

类似地,数字1是:

  • ≤ 2< 2≤ 1
  • ≤ 0< 0< 1

这是一张表格,显示了总体思路:

(注意:该表是一个很好的指导,但它的极限定义应该取决于上限而不是正常极限,例如, 3 + (n mod 2)永远在3到4之间振荡,它在O(1)尽管没有正常的限制,因为它仍然有一个限制:4.)

我建议记住Big-O符号如何转换为渐近比较。 比较容易记忆,但不够灵活,因为你不能说n O(1) = P。

Big-O符号O(n)Little-O符号o(n)什么区别?


我发现,当我无法从概念上理解某些东西时,想一想为什么要使用X有助于理解X.(并不是说你没有尝试过,我只是在设置舞台。)

[你知道的东西]对算法进行分类的一种常见方式是运行时,并且通过引用算法的大哦复杂性,可以很好地估计哪一个“更好” - 哪个具有“最小”函数在O! 即使在现实世界中,O(N)比O(N 2)“更好”,除非超级巨量常量等愚蠢的东西。[/你知道的东西]

假设有一些算法在O(N)中运行。 很好,是吧? 但是让我们说你(你这个聪明的人)提出了一个运行在O( N / loglogloglogN )中的算法。 好极了! 它更快! 但是当你写论文时,你会一遍又一遍地感到无聊。 所以你写了一次,你可以说“在本文中,我已经证明算法X,以前可以在时间O(N)上计算,实际上可以在o(n)中计算。”

因此,每个人都知道你的算法更快 - 多少不清楚,但他们知道它的速度更快。 理论上。 :)







little-o