单靠时间值绝对可信吗?
程序的运算离不开计算机环境(包括硬件和操作系统),这些客户原因都会影响程序运行的速度
所以,单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的!
时间复杂度与'大o记法'
对于算法的时间效率，我们可以用“大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.基本操作,即只有常数项,认为其时间复杂度为o(1)
2.顺序结构,时间复杂度按加法进行计算
3.循环结构,时间复杂度按乘法进行计算
4.分支结构,时间复杂度取最大值
5.判断一个算法的效率时,往往只需要关注操作数量的最高次项,其他次要项和常数项可以忽略
6. 在没有特殊说明时,我们所分析的算法的时间复杂度都是志最坏时间复杂 度
算法分析
1.第一次尝试算法核心部分
时间复杂度:
1.第二次尝试算法的核心部分
时间复杂度:
尝试第二种算法要比第一种算法的时间复杂度好多
