时间复杂度

O符号：

• 这个符号可以解释为：只要当排序元素的个数大于某个阈值N时，那么对于某个常量c > 0，运行时间最多为cn^2也就是说Ο符号提供了一个运行时间的上界。
• 定义 2-1 令 T(n)和 f(n)是非负函数，如果存在一个非负整数 N 以及一个常数 c>0，使得：

Ω符号

• Ο符号给出了算法时间复杂度的上界，而Ω符号在运行时间的常数因子范围内给出了时间复杂度的下界。Ω符号可以解释为：如果输入大于等于某个阈值 N，算法的运行时间下限是 f(n)的 c 倍，其中 c 是一个正常数，则称算法的时间复杂度是Ω(f(n))的。Ω的形式定义与Ο符号对称。

• 定义 2-2 令 T(n)和 f(n)是非负函数，如果存在一个非负整数 N 以及一个常数 c>0，使得：
  θ符号

• Ο符号给出了算法时间复杂度的上界，Ω符号给出了时间复杂度的下界，而θ给出了算法时间复杂度的精确阶。Θ符号可以解释为：如果输入大于等于某个阈值N，算法的运行时间在下限c1f(n)和上限c2f(n)之间（0<c1≤c2），则称算法的 时间复杂度是Θ(f(n))阶的。

• 定义 2-3 令T(n)和f(n)是非负函数，如果存在一个非负整数N以及常数c1>0 和c2>0，