1. 简介

• 一个算法语句总的执行次数是关于问题规模N的某个函数，记为 #card=math&code=f%28N%29)， 称为问题的规模。
• 语句总的执行次数记为 #card=math&code=T%28N%29)，当 不断变化时，#card=math&code=T%28N%29) 也在变化，算法执行次数的增长速率和f(N)的增长速率相同。
• 则有 %20%3D%20O(f(N))#card=math&code=T%28N%29%20%3D%20O%28f%28N%29%29)，这称作算法的渐进时间复杂度，简称时间复杂度。

2. 思想

1. 算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好地反映出算法的优劣与否。

2. 算法执行时间需要依据该算法编制的程序在计算机上执行运行时所消耗的时间来度量，度量方法有两种

   1. 事后统计方法
   2. 事前分析估算方法
   3. 因为事后统计方法更多地依赖计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣，因此常采用事前分析估算的方法。

3. 一个算法是由控制结构（顺序、分支、循环三种）和原操作（固有数据类型的操作）构成的，而算法时间取决于两者的综合效率。

4. 一个算法花费的时间与算法中语句的执行次数成正比，执行次数越多，花费的时间就越多，其执行次数称为语句频度或时间频度，记为 #card=math&code=T%28n%29)。

5. 在时间频度中，n为问题的规模，当n不断变化时，它所呈现出来的规律，我们称为时间复杂度。

6. 在各种算法中，若算法中的语句执行次数为一个常数，则时间复杂度为#card=math&code=O%281%29)，同时，若不同算法的时间频度不一样，但他们的时间复杂度却可能是一样的。

7. %3Dn%5E2%2B2n%2B4#card=math&code=T%28n%29%3Dn%5E2%2B2n%2B4) 对比 %20%3D%204n%5E2%2Bn%2B8#card=math&code=T%28n%29%20%3D%204n%5E2%2Bn%2B8)

   • 他们的时间频度显然不一样，但他们的时间复杂度却是一样的，均为

8. 时间复杂度只关注最高数量级，且与之系数也没有关系。

3. 最坏时间复杂度和平均时间复杂度

• 最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。

• 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间，设每种情况的出现的概率为 ,平均时间复杂度则为)#card=math&code=sum%28pi%2Af%28n%29%29) 。

4. 求解算法的时间复杂度

1. 找出算法的基本语句

   • 算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

2. 计算基本语句执行次数的数量级

   • 只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

3. 用大 记号表示算法的时间性能

   • 将基本语句执行次数的数量级放入大 记号中
   • 如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体
   • 如果算法中包含并列的循环，则将并列循环的时间复杂度相加

举例

for(i=1;i<=n;i++){
    a++
};
for(i=1;i<=n;i++){
    for(j=1;j<=n;j++)
    {
        a++;
    }
}

解析

1. 第一个for循环的时间复杂度为 #card=math&code=O%28n%29)
2. 第二个for循环时间复杂度为
3. 整个算法的时间复杂度为 #card=math&code=O%28n%5E2%2Bn%29)
4. #card=math&code=O%281%29) 表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，时间复杂度就为#card=math&code=O%281%29)

分析方法

1. 时间复杂度就是函数中基本操作所执行的次数
2. 一般默认的是最坏时间复杂度，即分析最坏情况下所能执行的次数
3. 忽略掉常数项
4. 关注运行时间的增长趋势，关注函数式中增长最快的表达式，忽略系数
5. 计算时间复杂度是估算随着n的增长函数执行次数的增长趋势
6. 递归算法的时间复杂度为：递归总次数 * 每次递归中基本操作所执行的次数
7. 常用的时间复杂度有以下七种，算法时间复杂度依次增加：#card=math&code=O%281%29)常数型、#card=math&code=O%28log2%C2%A0n%29)对数型、#card=math&code=O%28n%29)线性型、#card=math&code=O%28nlog2n%29)二维型、#card=math&code=O%28n%5E2%29)平方型、#card=math&code=O%28n%5E3%29)立方型、#card=math&code=O%282%5En%29)指数型。

https://zhuanlan.zhihu.com/p/50479555 （挖坑补充）

特殊时间复杂度

1. 二分查找

   • 因为每次的计算，都可以把查找的范围缩小一半，所以二分查找的时间复杂度为#card=math&code=O%EF%BC%88log2%20N%29)。

2. 斐波那契的递归算法

   • 因为每次的展开都要把当前的已知项再拆分成当前数目的两倍，所以斐波那契的递归算法时间复杂度为#card=math&code=O%282%5EN%29)。
   • 斐波那契的时间复杂度算法如下图所示，计算n第N个斐波那契数的大小时，共需计算次。

常用排序算法的时间复杂度