当输入规模足够大，执行时间只与增长量水平相关时，需要研究算法的渐近效率。 也就是说，输入规模无限增加时，在极限中，算法的执行时间如何随着输入规模的增大而增加？ 本文使用的插图来自《算法导论》。
不同的符号从不同的侧面刻画一个算法的执行效率。 插入排序的最差执行时间由以下公式表示：
f(n) = an2+bn+c其中a、b、c是常数，n是输入尺寸。 对插入排序的最坏运行时间f(n)进行讨论
根据与f(n )的大小关系，分为“==”、“=”、“=”、“=”、“”共5种符号，分别如下
(theta ) (=) o ) )大o ) ) ) o ) )混乱的猫) )渐进地边界c1，c2为某个正常量，n大于某个值时满足3358www
插入顺序最差的运行时是0 = c1g(n) = f(n) = c2g(n)
最差运行时间： t(n )==) g ) n ) )==) n2 )。 渐近正函数的低阶项在确定渐近确定界时可以忽略。 对于大的n，它们并不重要，因为当n大时，高次项的小部分能够支配所有低次项。
如下图所示。
2、o (大o )上界c为某个正常量，当n大于某个值时，为f(n) = an2+bn+c
插入顺序最差的运行时是cg(n) = f(n)
最差运行时间f(n) = an2+bn+c
如下图所示。
3、o )模糊猫)非渐近的确定性上界的任意正常量c，当n大于某w一定值时，为**f(n ) CG ) n ) *
例如，某个算法的执行时间由以下公式表示。T(n) == O(g(n)) == O(n2)
算法运行时间：f(n) = 2n
o和o的区别：
对于大于0的常数c，确定f(n )=o ) g(n )，0=f (n )=CG (n )。
f(n )=o ) g(n )，0=f ) n )=CG ) n )对于所有大于0的常数c都成立。
4、(大欧米茄)下界o印给出一个函数的渐近上界，印给出渐近下界。
c为某正常量，当n大于某一值时，为T(n) == o(g(n)) == o(n2)
算法运行时间：0 c(g(n)) f(n)
5、)模糊负片(非渐近确实下界标记与标记的关系类似于o标记与o标记的关系。
对于任意正常量c，当n大于某个值时，T(n) == o(g(n)) == o(n2)
算法的执行时间： **t(n )==o ) g ) n ) )