时间复杂度，超级详细_平均时间复杂度

6.2 算法的时间复杂度

度量一个程序（算法）执行的两种方法

• 1）事后统计的方法

  这种方法可行，但是有两个问题：一是想对设计的算法的运行性能进行评测，需要实际运行该程序：二是所得时间统计量依赖计算机的硬件、软件等环境因素，这种方式要在同一台计算机相同状态运行下，才能比较哪个算法速度快

• 2）事前估算的方法

  通过分析某个算法的时间复杂度来判断哪个算法更优 。

6.2.1 时间频度

基本介绍

时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度记为T（n）。

先给出几个结论：

结论：忽略常数项

结论：忽略低次项

结论：忽略系数

6.2.2 时间复杂度

• 1）一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T（n）表示，若有某个辅助函数f（n），使得当n趋近无穷大时，T（n）/ f（n）的极限值不等于零的常熟，则称f（n）是T（n）同数量级别的函数。记作T（n） = O （f（n）），称 O （f（n））为算法的渐进时间复杂度，简称时间复杂度。
• 2）T（n）不同，但是时间复杂度可能相同。
• 计算时间复杂度的方法：
  • 用常数1代替运行时间中所有加法常数
  • 修改后的运行次数函数中，只保留最高阶项
  • 去除最高阶项的系数。

6.2.3 常见的时间复杂度

1）常数阶O（1）

2）对数阶O（log2n）

3）线性阶O（n）

4）线性对数阶O（nlog2n）

5）平方阶O（n²）

6）立方阶O（n³）

7）k次方阶O（n的k次方）

8）指数阶O（2的n次方）

//一定要死死记住时间复杂的大小顺序，最好把它刻在DNA上

1）常数阶O（1）

无论代码执行了多少行，只要没有循环等复杂结构，那么这个代码的时间复杂度就是O（1）

2）对数阶O（log2n）

例子：a的x次方等于N，那么x叫以a为底N的对数，记作x = logaN。其中

a叫对数的底数，N 叫做真数，x叫做“以a为底N的对数”
说实话，对数阶O（log2n），我坐在电脑前枯想十几分都没有头绪，于是我尝试动手画一下操作流程，大概就懂了七八分。

3）线性阶O（n）

4）线性对数阶O（nlog2n）

5）平方阶O（n²）

之后的我就不截图了，这几个都比较好理解，所以就不一一放出来了

6）立方阶O（n³）

7）k次方阶O（n的k次方）

8）指数阶O（2的n次方）

6.3 最坏时间复杂度

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

1）平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间

2）最坏情况下的时间复杂度称为最坏时间复杂度。一般讨论的时间复杂度均是以最坏情况下的时间复杂度，原因：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法 的运行时间不会比最坏情况更长

3）平均时间复杂度和最坏时间复杂度是否一致，和算法有关

6.3 空间复杂度

6.3.1 基本jieshao

1）类似时间复杂度的讨论，一个算法的空间复杂度（space Complexity）定义为该算法所消耗的存储空间，它是问题规模n的函数

2）空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，入如快速排序和归并排序算法就是属于这种情况

3）在做算法分析时在，主要讨论的是时间复杂度，从用户使用体验上看，更看重程序执行的速度，一些缓存产品（redis、memcache）和算法（基数排序）的本质就是用空间换时间。

本次时间复杂度教程出自韩顺平的数据结构和算法教程

数据结构和算法教程
哔哩哔哩详细教程
在 51-53p，视频共有三个，不到一个小时。二倍速半小时即可看完。
最后，认识一下，我是小白。努力成为一名合格的程序员。期待与你的下次相遇。