如何衡量一个算法的优劣？
一、事后统计的方法
让算法先在电脑上跑一下，整一个计时器来算一下执行一次运行了多长时间。
缺点：
- 同一台电脑，在运行同一个程序，执行同一个任务的时候，占用的时间和计算机当时很多状况有关系（cpu，内存占用等情况），所以不准确。
结果：不可信
二、事前分析估算的方法
1、相关概念
语句频度T(n)
- 一个算法中的语句执行次数：称为语句频度，记为：T(n)。
2、引入
例子：计算1~100的数字之和
算法一：使用for循环计算
int sum = 0;
int endNum = 100;
//使用for循环计算
for(int i = 1; i <= endNum; i++){
sum += i;
}
- 首先：endNum = 100的时候就要执行100次，1000就执行1000次
- 此时i = 100时，还需要在判断一次101。
- 【总共执行101次】所以为：T(n) = n + 1
算法二：直接计算
int sum = 0;
int endNum = 100;
//直接计算
sum = (1 + endNum) * endNum / 2;
- 无论执行到多少100,1000…都执行一次
- 【总共执行一次】所以为：T(n) =1
3、时间复杂度和空间复杂度一般忽略的参数
忽略常数：
忽略低次项：
忽略系数：
4、时间复杂度【常用】-（相应算法在计算过程中要占用多少时间）
(1)概念
- 一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记住：T(n) = O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称：时间复杂度。
- 简要：O(f(n))就是时间复杂度
- 注：n就是问题的规模，要做事情的多少
(2)对于不同的算法而言：语句频度T(n)不同，但是时间复杂度O(f(n))可能相同
- 如：
T(n) = n^2+5n+6与T(n) = 3n^2+3n+2它们的T(n)不同，但时间复杂度相同，都为O(n^2)； - 其实时间复杂度就下面这些常见。
(3)常见的时间复杂度
- 常数阶：O(1)
- 不管算法执行几次，只要是个常数就符合
- 对数阶：O(log^2n)
- 线性阶：O(n)
- 线性对数阶：O(nlog^2n)
- 平方阶：O(n^2)
- 立方阶：O(n^3)
- k次方阶：O(n^k)
- 指数阶：O(2^n)
- 【由上往下】随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
(4)计算时间复杂度的方法
- 先要知道自己的算法是怎么写的。
- 然后写出对应的语句频度T(n)—如：T(n) = 3n^2 + 2n + 1
- 用常数1代替运行时间中的所有加法常数**—如：T(n) = 1n^2 + 1n + 1**
- 修改后的运行次数函数中，只保留最高阶项**—如：T(n) = 1n^2**
- 去除最高阶项的系数**—如：T(n) = n^2**
(5)平均时间复杂度和最坏时间复杂度
平均时间复杂度是指：所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
最坏时间复杂度【常用】是指：一般讨论的时间复杂度均是最坏情况下的时间复杂度。
- 这样做到原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。
5、空间复杂度【不常用】-（相应算法在运行过程中要占用多少内存）