执行时间反应算法效率

• 实现算法程序的执行时间可以反应出算法的效率，即算法的优劣

单靠时间值绝对可信吗

• 单纯依靠时间来比较算法的优劣并不一定是客观准确的！

时间复杂读与“大O记法”

• “大O记法” 对于单调的整数函数F，如果存在一个整数函数G和实常数 C > 0,使得对于充分大的N总有F(n) < c*g(n), 就说函数G是F的一个渐进函数（忽略常数），记为f(n)=O(g(n))， 也就是说，在趋向无穷的极限意义下，函数f的增长速度受到函数g的约束，亦即函数f与函数g的特征相似。
• 时间复杂度：假设存在函数g，使得算法A处理规模为N的问题示例所用时间为T(n)=O(g(n)), 则称O(g(n))为算法A的渐进时间复杂度，简称时间复杂度，记为T(n).

最坏时间复杂度

• 分析算法，最优时间复杂度（算法完成工作最少需要多少基本操作）
• 最坏时间复杂度（算法完成工作最多需要多少基本操作）
• 平均时间复杂度（算法完成工作平均需要多少基本操作）
• 我们主要关注最坏时间复杂度

时间复杂度的几条基本计算规则

• 基本操作，即只有常数项，认为其时间复杂度为O(1)
• 顺序结构，时间复杂度按加法进行计算
• 循环结构，时间复杂度按乘法进行计算
• 分支结构，时间复杂取最大值
• 判断一个算法的效率时，往往只需要关注操纵数量的最高次项，其他次要项和常数项可以忽略
• 在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度。

常见时间复杂度

• 2n+3 —–> O(n)
• 3n^2+2n+1 —–> O(n^2)
• 5log2n+20 —-> O(logn)
• 2n+3nlog2n+19 —->(nlogn)
• 6n^3 + 2n^2 + 3n +4 —->(O(n^3))
• 2^n —->(O(2^n))
• 注意，经常将log2n(以2为底的对数)简写成logn

常见时间复杂度之间的关系

• 所消耗的时间从小到大
• O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)