文章标题：
数据结构中算法复杂度的全面剖析
文章内容：
文章目录
- 1. 算法复杂度
- 1.1 数据结构
- 1.2 算法
- 1.3 两者的重要性
- 2. 算法效能
-
- 热身问题：
- 复杂度概念
- 3. 时间复杂度
-
- 3.1 大O表示法
- 3.2 时间复杂度示例练习
-
- 示例1
- 示例2
- 示例3
- 示例4
- 示例5
- 示例6
- 示例7
- 4. 空间复杂度
-
- 4.1 空间复杂度示例练习
-
- 示例1
- 示例2
- 5. 热身问题拓展
-
- 5.1 思路2：运用空间换时间的办法
- 5.2 思路3(优化解)：
1. 算法复杂度
1.1 数据结构
数据结构是计算机存储与组织数据的方式，是相互间存在特定关系的数据元素集合。不存在一种数据结构适用于所有场景，所以需学习各类数据结构，如线性表、树、图、哈希等。
1.2 算法
算法是定义清晰的计算流程，它以一个或一组值为输入，输出一个或一组值。简单说，算法是将输入数据转化为输出结果的一系列计算步骤。
1.3 两者的重要性
研究算法与数据结构的最终目的是实现“快”与“省”，“快”指运行速度快，“省”指消耗硬件资源少。讨论数据结构与算法时，必然涉及复杂度分析，包括时间复杂度和空间复杂度分析。
随着信息技术发展，大内存设备常见，但仍不能忽视空间复杂度。
小引：摩尔定律
集成电路上可容纳的晶体管数目大约每18到24个月就会增加一倍。也就是说，处理器性能大约每两年翻倍，同时价格降为之前的一半。摩尔定律是内行人摩尔的经验之谈，虽非自然科学定律，但一定程度揭示了信息技术进步的速度。
2. 算法效能
如何评判一个算法的优劣呢？
热身问题：
轮转数组
代码实现：
代码运行结果：
可以看到我们通过了37个测试用例，但在某个用例上超出了时间限制，这是什么原因呢？
查看题目提示
如果数组非常大，且需要轮转90次，就会超出时间限制。
那么，如何评判算法的好坏呢？为此需要引入复杂度的概念。
复杂度概念
算法编写成可执行程序后，运行时会消耗时间资源和空间（内存）资源。因此，评判一个算法的优劣，通常从时间和空间两个维度考量，即时间复杂度和空间复杂度。
时间复杂度主要衡量算法的运行快慢，而空间复杂度主要衡量算法运行所需的额外空间。
3. 时间复杂度
定义：在计算机科学中，算法的时间复杂度是一个函数T(N)，它定量描述算法的运行时间。时间复杂度用于衡量程序的时间效率，那为何不直接计算程序的运行时间呢？
-
因为程序运行时间与编译环境和运行机器配置有关，比如同一算法程序，用老编译器编译和新编译器编译，在相同机器上运行时间不同。
-
同一算法程序，用老低配置机器和新高配置机器，运行时间也不同。
- 并且时间只能在程序编写后测试，不能在编写前通过理论思想计算评估。
这是我在vs编译器x64位环境下，通过冒泡排序运行3次将100000个数排成升序各自所需的时间，所以我们不直接计算程序运行时间。
那么算法的时间复杂度函数T(N)到底是什么呢？这个T(N)函数计算程序的执行次数。在编译链接过程中，算法程序编译生成二进制指令，cpu执行这些指令。我们通过程序代码或理论思想计算程序执行次数的函数T(N)，假设每条指令执行时间基本相同（实际有差异，但微乎其微），那么执行次数与时间呈等比正相关，这样就脱离了具体编译运行环境。执行次数可代表程序时间效率的优劣。比如解决同一问题的算法a程序T(N)=N，算法b程序T(N)=N²，那么算法a的效率一定优于算法b。
实际计算时间复杂度时，我们计算的不是程序精确的执行次数，精确计算很麻烦（不同程序代码编译出的指令条数不同），精确执行次数意义不大，因为我们计算时间复杂度是想比较算法程序的增长量级，当N不断增大时，常数和低阶项影响很小，所以只需计算能代表增长量级的大概执行次数，复杂度通常用大O渐进表示法表示。
3.1 大O表示法
什么意思呢？
以Func1为例，T(N)=N²+2N+10。
根据大O阶第一条规则：只保留最高阶项，O(N)=N²。
3.2 时间复杂度示例练习
示例1
Func2执行的基本操作次数：
T(N)=2N+10
根据推导规则第3条得出：
Func2的时间复杂度为：O(N)
示例2
T(N)=M+N
因此：Func2的时间复杂度为：O(N)
示例3
T(N)=100
根据推导规则第1条得出
Func2的时间复杂度为：O(1)
示例4
strchr执行的基本操作次数：
（1）若要查找的字符在字符串第一个位置，
则：T(N)=1
（2）若要查找的字符在字符串最后一个位置，
则：T(N)=N
（3）若要查找的字符在字符串中间位置，
则：T(N)=N/2
因此：strchr的时间复杂度分为：
最好情况：O(1)
最坏情况：O(N)
平均情况：O(N)
由于大O表示法一般表示最坏情况，即O(N)
示例5
（1）若数组有序，
则：T(N)=N,O(N)
（2）若数组有序且为降序，
则：T(N)=N*(N+1)/2,即O(N²)
因此：BubbleSort的时间复杂度取最差情况为：O(N² )
示例6
当n=2时，执行次数为1
当n=4时，执行次数为2
当n=16时，执行次数为4
假设执行次数为x，则2x=n
因此执行次数：x=log n
因此：func5的时间复杂度取最差情况为：O(log₂ n)
提问：那么log₂n,logn,lgn等有区别吗？
没有区别，我们关注的是增长量级，当n越来越大时，底数对结果的影响可忽略，所以这些表示方法都可以。
示例7
调用一次Fac函数的时间复杂度为O(1)
而在Fac函数中，存在n次递归调用Fac函数
因此：阶乘递归的时间复杂度为：O(n)
算递归复杂度的万能公式：创建了多少次函数栈帧（递推了多少次）*单次递归执行的次数。
4. 空间复杂度
空间复杂度也是数学表达式，是算法运行过程中因算法需要额外临时开辟的空间。空间复杂度不是程序占用了多少bytes空间，因为常规情况对象大小差异不大，所以空间复杂度算的是变量个数。
空间复杂度计算规则基本同时间复杂度，也使用大O渐进表示法。
注意：函数运行时所需栈空间（存储参数、局部变量、一些寄存器信息等）在编译期间已确定，所以空间复杂度主要通过函数运行时显式申请的额外空间确定。
4.1 空间复杂度示例练习
示例1
BubbleSort额外申请的空间有exchange，end等有限个局部变量，使用常数个额外空间。
相关文章
