本文共 601 字，大约阅读时间需要 2 分钟。

1.算法时间复杂度:Ω-Θ-T(自下而上)

---

大 O 记号

如果存在正常数 a、 N 和一个函数 f(n)，使得对于任何 n > N，都有

T(n) < a × f(n)

我们就可以认为在 n 足够大之后， f(n)给出了 T(n)的一个上界。对于这种情况，我们记之为

T(n) = O(f(n))

这里的 O 称作“大 O 记号（ Big-O notation）”。

---

大Ω记号

如果存在正常数 a、 N 和一个函数 g(n)，使得对于任何 n > N，都有

T(n) > a × g(n)

我们就可以认为在 n 足够大之后， g(n)给出了 T(n)的一个下界。对于这种情况，我们记之为

T(n) = Ω(g(n))

这里的Ω称作“大Ω记号（ Big-Ω notation）”。

大Ω记号与大 O 记号正好相反，它是对算法执行效率的一种乐观估计⎯⎯对于规模为 n 的任意 输入，算法的运行时间都不会低于Ω(g(n))。

---

Θ记号

如果存在正常数 a<b、 N 和一个函数 h(n)，使得对于任何 n > N，都有

a × h(n) < T(n) < b × h(n)

我们就可以认为在 n 足够大之后， h(n)给出了 T(n)的一个确界。对于这种情况，我们记之为

T(n) = Θ(h(n))

Θ记号是对算法执行效率的一种准确估计⎯⎯对于规模为 n 的任意输入，算法的运行时间都与

Θ(h(n))同阶。

---

转载地址：http://powji.baihongyu.com/