在表示算法的时间复杂度上 ， 我们通常会使用渐进符号
常用的渐进符号有 ：O ，Ω ，θ
那么这三个符号分别表示了什么含义呢
O( f(n) ) : 给出了算法运行时间的上界 ， 也就是最坏情况下的时间复杂度
Ω( f(n) ) : 给出了算法运行时间的下界 ， 也就是最好情况下的时间复杂度
θ ( f(n) ) : 给出了算法运行时间的上界和下界 ， 这里 θ ( f(n) ) 是渐进的确界
首先 ， 这三个符号 ， 并不一定都和算法分析有关 ， 这三个符号只是用来刻画函数的增长速度的 ， 假如有函数 ： f(n) = 3n^2 + 100n + 1000， 那么我们就可以说 f(n) = O(n^2) = O(n^3) , f(n) = Ω(n^2) = Ω(n) , f(n) = θ(n^2) 。
当具体到算法复杂度分析上，比如说插入排序。在最坏的情况下(原序列是倒序) ,如果我们仔细计算此时需要的比较和交换次数 , 会发现它是一个 f(n)=An^2+..的形式 , 于是我们可以说:
插入排序在最坏情况下的时间复杂度是:θ(n^2) , 也是O(n^2) ,也是Ω(n^2) 。
在最好的情况下(原序列已经有序)的时间复杂度是 ： θ(n) ， O(n) ，也是Ω(n) 。
如果在非特定条件下 ，插入排序(在所有情况下)的时间复杂度是多少呢 ？ 这个时候就不能使用θ来回答了 ， 因为最好情况和最坏情况的θ是不同的 ， 所以我们只能说 ，在所有情况下它的时间复杂度都是O(n^2) ，也可以回答 ， 在所有的情况下都是Ω(n)；
