时间复杂度

解决同一个问题的多种方法的好坏区分？

执行效率是算法一个非常重要的考量，如何衡量一个算法的执行效率呢？
数据结构和算法本身的为了解决“快”和“省”的问题，所谓的“快”和“省”具体指什么？

1. 代码运行的时间更快，运行占用的空间更少！
2. 快-时间复杂度
3. 省-空间复杂度

为什么要进行复杂度分析

大家知道我们程序写出来，运行一遍就知道占用的内存大小，那么为什么还要做复 杂度分析呢？运行程序得出的结果在专业上叫着事后统计法
事后统计法的缺点：

• 测试依赖于环境，不同的环境显示结果不一样
• 测试结果受数据规模影响很大

基于上诉原因，我们需要一个不需要具体的测试数据就能粗略估计算法执行效率的 方法

为什么要进行时间复杂度分析

如何在不执行代码的情况下，分析代码的执行效率？ 从CPU的角度来看，对于每一行代码做的都是同一件事，读数据-运算-写数据

1. 时间复杂度分析-实例1

假设每行代码对应的CPU执行时间一样为一个时间单位unit_time。可以看到这个函数代码第2，5行执行1次，第3，4行执行了n次，总共执行时间计算：
T(n)=2unit_time+2unit_timen=(2+2n)*unit_time

2. 时间复杂度分析-实例2

假设每行代码对应的CPU执行时间一样为一个时间单位unit_time。可以看到这个函数代码第2，5行执行n次，第3，4行执行了nxn次，总共执行时间计算：
T(n)=2unit_timen+2unit_timen²=(2n+2n²)*unit_time

时间复杂度分析

尽管我们不知道一个unit_time的具体时间是多少，但是我们通过实例1和实例2可以推 导出代码是执行时间与执行次数n正比，我们讲这个规律总结成公式
T(n) = O(f(n))
  • T(n)：代码的执行时间
  • n：数据的规模
  • f(n)：每行代码执行的次数总和
  • O：表示T(n)与f(n)正比关系
大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据 规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度

时间复杂度分析

当 n 很大时，你可以把它想象成 10000 、 100000 。而公式中的低阶、常量、系数三 部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以 了，如果用大O表示法表示刚讲的那两段代码的时间复杂度，就可以记为：
实例一：T(n) = O(n)；
实例二：T(n) = O(n2 )；
注意!!!即便某一段代码循环 10000 次、 100000 次，只要是一个已知的数，跟 n 无关， 照样也是常量级的执行时间。当 n 无限大的时候，就可以忽略.

如何对一段代码进行时间复杂度分析

1. 只关注循环执行次数最多的一段代码：
大O这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、 低阶、系数，只需要记录一个最大阶的量级就可以了，分析一个算法、一段代码的 时间复杂度的时候，只关注循环执行次数最多的那一段代码就可以了
2. 总复杂度等于量级最大的那段代码的复杂度

3. 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积-实例2

几种常见的时间复杂度实例分析

常见复杂度量级详解-非多项式量级

数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执 行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法

常见复杂度量级详解-多项式量级O(I)

O(I) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如 下面这段代码，即便有 5行，它的时间复杂度也是 O(I）
• print(1)
• print(2)
• print(3)
• print(4)
• print(5)

常见复杂度量级详解-多项式量级O(LOGN)

对数阶时间复杂度非常常见,但是非常难以分析

通过前面的复杂度分析方法知道第3，4行代码是执行次数最多的行数，要求出这段代码的时间复杂度，我 们只需要求出第3，4行代码的执行次数即可

变量 i 的值从 1 开始取，每循环一次就乘以 2 。当大于 n 时循环结束，所以变量 i 的取值就是一个等比 数列 2⁰ 2¹ 2² 2³ 2ⁱ==n ,所以代码执行的次数i=log2ⁿ

对数阶时间复杂度非常常见,但是非常难以分析

修改代码后，变量 i 的值从 1 开始取，每循环一次就乘以 3 。当大于 n 时循环结束，所以 变量 i 的取值就是一个等比 数列 3⁰ 3¹ 3² 3³ 3ⁱ==n ,所以代码执行的次数i=log3ⁿ

对数之间是可以互相转换的，log3ⁿ就等于log3² * log2ⁿ，所以O(log3ⁿ) = O(C * log2ⁿ)，其中C=log 3 2是一个常量。基于我们前面的一个理论：在采用大O标记复 杂度的时候，可以忽略系数，即O(Cf(n)) = O(f(n))。所以，O(log2ⁿ) 就等于O(log3ⁿ)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示 为 O(logn) 。

常见复杂度量级详解-多项式量级O(NLOGN)

理解了O(logn) ，那 O(nlogn) 就很容易理解了。如果一段代码的时间复杂度是 O(logn) ，同时循环 执行 n 遍，时间复杂度就是 O(nlogn) 了

常见复杂度量级详解-多项式量级O(M+N)、O(M*N)