我知道算法的时间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)) or O(g(n))，但没有解释为什么会这样Ɵ or 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). 请注意，mergesort也是， O(n^2)因为它不比. （人们通常不会这样描述它，但这就是正式符号的含义。）n^2
对于某些算法，我们不知道严格的界限；简单计算模型中的一般3SUM 问题是众所周知的，Ω(n lg n)因为它可以用于执行排序，但我们只有Ɵ(n^2)算法。该问题的最佳算法在n lg n和之间n^2；我们可以说它是O(n^2)and Ω(n lg n)，但我们不知道Ɵ。
还有o(f), 表示严格小于f, and ω(f), 表示严格大于f。
我熟悉的定义是 T(n) 是 Ω(g(n)) if for some n0, for all n>n0, T(n) >= g(n)*kfor some k。
然后某物是 Θ(n) 当且仅当它是 O(g(n)) 和 Ω(g(n))。