我理解算法的时间 T(n) 可以由 O(g(n)) 定义:
T(n) is O(g(n)) iff there is a c > 0, n0 > 0, such that for all n >= n0:
对于大小为 n 的每个输入， A 最多需要 c * g(n) 步。
T(n) 是所有大小为 n 的输入中最长的时间。
但是我不明白的是 Ω(g(n)) 的定义。定义是对于大小为 n 的一些输入，A 至少需要 c * g(n) 个步骤。
但是如果那是 Ω 的定义，那么我不能找到与上限相同的任何算法的下限吗？例如，如果在最坏的情况下排序需要 O(nlogn) 那么我将无法轻松显示 Ω(nlogn) 以及看到必须如何对于任何大小 n 至少有一个错误输入需要 nlogn 步骤？假设我们正在讨论 heapsort。
我真的不确定我在这里遗漏了什么，因为每当我被教导一种新算法时，某种方法的时间要么是 Ɵ(g(n)) 要么是 O(g(n))，但没有解释为什么它是 Ɵ 或 O。
我希望我说的足够清楚，如果还不清楚，请提出您误解的地方。我真的需要澄清这种困惑。谢谢。
最佳答案
O是一个上限，这意味着我们知道一个算法是 O(n lg n)渐进地，至多需要常数次n lg n最坏情况下的步骤。
Ω是一个下限，这意味着我们知道 Ω(n lg n) 是不可能的渐近小于 n lg n 的算法最坏情况下的步骤。
Ɵ是紧界:例如，如果算法是 Ɵ(n lg n)然后我们知道两者都是O(n lg n) (因此至少与 n lg n 一样快)和 Ω(n lg n) (所以我们知道它不比 n lg n 快)。
你的论点有缺陷的原因是你实际上假设你知道 Ɵ(n lg n) ，不只是 O(n lg n) .
例如，我们知道有一个 Ω(n lg n)比较排序的一般界限。一旦我们证明了O(n lg n)对于合并排序，这意味着合并排序是 Ɵ(n lg n) .请注意，合并排序也是 O(n^2) ，因为它不慢 n^2 . (这不是人们通常描述它的方式，但这是正式符号的意思。)
对于某些算法，我们不知道紧界；将军3SUM problem在简单的计算模型中已知为 Ω(n lg n)因为它可以用来进行排序，但是我们只有Ɵ(n^2)算法。该问题的最佳算法介于 n lg n 之间。和 n^2 ;我们可以说它是O(n^2)和 Ω(n lg n) , 但我们不知道 Ɵ .
还有 o(f) , 这意味着严格小于 f , 和 ω(f) , 这意味着严格大于 f .
关于algorithm - 我真的很困惑时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10135174/