TOC
最近在重新复习算法，所以翻了下算法导论，查阅了点资料，记录下渐进符号。
O
读作 大 O 拉丁字母 O
描述一个函数数量级的渐近上界
O(g(n)) = f(n) , 存在正常量 c 和 n0 使得对所有 n >= 0 , 有 0 <= f(n) <= cg(n)
函数最烂的情况到底有多烂
Ω
读作大 Omega
描述一个函数数量级的渐近下界
Ω(g(n)) = f(n) , 存在正常量 c 和 n0 使得对所有 n >= n0 , 有 0 <= cg(n) <= f(n)
函数最好的情况到底有多好
Θ
读作 大 Theta
描述一个函数数量级的渐近下界与渐进上界
Θ(g(n)) = f(n) , 存在正常量c1,c2和n0,使得对所有n >= n0,有 0 <= c1g(n) <= f(n) <= c2g(n)
就是上面两个合体一下
O 和 Ω 都有对应的小版本，主要区别就是对某个常量C成立变成对所有常量C成立，会造成在极限概念下，当N足够大的时候，结果的区别，这里就不做记录了，因为与用的非常少