O(n)和Little-O表示法o(n)有什么区别？#1 楼
f∈O（g）本质上说对于常数k> 0的至少一个选择，您可以找到一个常数a使得不等式0 <= f（x） <= kg（x）适用于所有x> a。
请注意，O（g）是满足该条件的所有函数的集合。
f∈o（g）本质上说
对于常数k> 0的每个选择，您都可以找到常数a，使得不等式0 <= f（x）
在Big-O中，仅需要找到一个特定的乘数k不等式超过了最小x。
在Little-o中，必须确保存在一个最小值x，只要您使k不为负或为零，不等式就不管您成多小都成立。 br />这两者都描述了上限，尽管有点违反直觉，Little-o是更强有力的陈述。如果f∈o（g），则f和g的增长率之间的差距比f∈O（g）时大得多。
差异的一个例证是：f∈O（f）为真，而f∈o（f）为假。因此，Big-O可以理解为“ f∈O（g）意味着f的渐近增长不快于g's，而“ f∈o（g）意味着f's的渐近增长严格快于g's”。就像
<=与<一样。更具体地说，如果g（x）的值是f（x）的常数倍，则f∈O（g）为真。这就是为什么在使用big-O表示法时可以删除常量的原因。但是，要使f∈o（g）为真，则g必须在其公式中包含x的更高幂，并且因此f（x）和g（x）之间的相对距离实际上必须随着x变大而变大。
仅使用数学示例（而不是引用算法）：
以下内容适用于Big-O，但如果使用little-o则不适用：
x²∈O（x²）
x²∈O（x² + x）
x²∈O（200 *x²）
以下情况适用于little-o：
x²∈o（x³）
x²∈o （x！）
ln（x）∈o（x）
请注意，如果f∈o（g），则意味着f∈O（g）。例如x²∈o（x³），因此x²∈O（x³）也成立（再次，将O视为
<=和o视为<）#2 楼
大O对小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)中，因为它仍然具有lim sup：4。）我建议记住Big-O表示法如何转换为渐进比较。比较比较容易记住，但灵活性较差，因为您无法说出nO（1）= P之类的信息。
评论
我有一个问题：第3行和第4行（限制定义列）有什么区别？您能举一个4成立（lim> 0）而不是3的例子吗？
–蒙面人
2014年1月21日，5：08
哦，我知道了。 Big Omega适用于lim> 0，Big Oh适用于lim
–蒙面人
2014年1月21日，下午5:16
对于f∈Ω（g），不应该将无穷大的极限计算为> = 1吗？同样对于f∈O（g），1 =
–user2963623
2015年8月22日在7:16
@ user2963623否，因为严格高于0的有限值（包括0到1之间的值）对应于“相同的渐进复杂度，但是不同的常数因子”。如果您忽略小于1的值，则在常量因子空间而不是渐近复杂性空间中将有一个截止点。
– Craig Gidney
15年8月22日在13:52
@ubadub您在集合上广播了幂运算。这是个松散的符号。
– Craig Gidney
18/12/18在23:04
#3 楼
我发现，当我无法从概念上掌握某些内容时，思考为什么要使用X有助于理解X。（不是说您还没有尝试过，我只是在做准备。） br /> [您知道的东西]一种常见的算法分类方法是通过运行时，并通过引用算法的大哦复杂度，您可以很好地估算出哪种算法“更好”，无论哪种算法具有最小”功能！即使在现实世界中，O（N）也比O（N²）“更好”，除非有超质量常数之类的愚蠢事物。[/ stuff you know]在O（N）中运行的算法。还不错吧？但是，假设您（您的才华横溢的人）提出了以O（N⁄loglogloglogN）运行的算法。好极了！它更快！但是，当您撰写论文时，您会一遍又一遍地写作而感到愚蠢。因此，您只需编写一次，就可以说：“在本文中，我证明了以前可以在时间O（N）进行计算的算法X实际上可以在o（n）进行计算。”因此，每个人都知道您的算法更快-还不清楚多少，但是他们知道它更快。从理论上讲。 :)#4 楼
一般而言，渐近符号可以理解为：缩小时函数如何比较？ （测试这一点的一种好方法就是简单地使用Desmos之类的工具并用鼠标滚轮玩游戏）。特别是：f(n) ∈ o(n)意味着：在某一点上，缩小得越多，f(n)将由n主导更多（它将逐渐偏离它）。g(n) ∈ Θ(n)的意思是：在某个时候，缩小不会改变g(n)与n的比较（如果我们从轴上删除刻度，您将无法分辨出缩放级别）。函数h(n) ∈ O(n)可以属于这两种类别。它看起来可能很像h，或者当n增加时，它可能会越来越小。基本上，n和n都在f(n)中。在计算机科学中，人们通常会证明给定算法同时接受
g(n)的上限和O(n)的下限。当两个边界都满足时，这意味着我们找到了一种渐近最优算法来解决该特定问题。例如，如果我们证明算法的复杂度在O和𝛺中，则意味着它的复杂度在O(n)中。这就是𝛺(n)的定义，它或多或少地转化为“渐近相等”。这也意味着没有算法可以解决Θ(n)中的给定问题。同样，粗略地说“无法在不到Θ个步骤的时间内解决此问题”。o(n)的上限只是意味着即使在最坏的情况下，该算法也将最多以n步长终止（忽略所有常数因子，包括乘法和加法）。相反，O(n)的下限意味着我们建立了一些示例，这些示例无法用不到n的步长（再次忽略乘法和加法常数）解决此算法所解决的问题。步骤数最多为𝛺(n)，至少为n，因此此问题的复杂度为“正好为n”。每次写Q4312079q时，我们不必说“忽略常数乘/加因子”。
评论
是的-区别在于两个函数是否在渐近上相同。直觉上，我喜欢想到“大-O”的意思是“增长不快于”（即以相同的速度或更慢的速度增长），而“小-O”的意思是“增长严格于”。
–菲尔
09年9月1日于20:38
复制到维基百科？这比那里的要好得多。
– cloudsurfin
2014年11月9日下午4:42
@SA是的。这是一个棘手的情况，其中我给出的关于“ x的更高幂”的简单规则显然不适用。但是，如果您查看下面Strilanc的答案中给出的更严格的限制定义，您想知道的是lim n-> inf（2 ^ n / 3 ^ n）=0。因为（2 ^ n / 3 ^ n） =（2/3）^ n并且由于对于任何0 <= x <1，lim n-> inf（x ^ n）= 0，的确是2 ^ n = o（3 ^ n）。
–泰勒·麦克亨利（Tyler McHenry）
16 Jan 17'5:02
请注意“在Little-o中，必须确保存在一个最小值x，只要您不使k变小，只要不为负数或为零，不等式就成立。”不是“每有一个k：...”，而是“每有一个k：...”。
– GA1
19年5月15日在10:30
“在Little-o中，必须保证存在一个最小值x，只要将k设为负数或为零，无论将k设为多小，不等式都成立。”不，这是不正确的。
–菲利波·科斯塔（Filippo Costa）
3月4日13:20