数据结构之算法复杂度(超详解)

在这里插入图片描述

文章目录

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 数据结构

数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在⼀种或多种特定关系的数据元素的集合。没有⼀种单⼀的数据结构对所有用途都有用，所以要学各式各样的数据结构，如：线性表、树、图、哈希等。

1.2 算法

算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是⼀系列的计算步骤，用来将输入数据转化成输出结果。

1.3 二者的重要性

研究算法和数据结构的最终目的就是为了 “快” 和 “省”，快是指速度快，省是指耗费的内存等硬件资源少。而讨论数据结构和算法，必然涉及复杂度分析。包括时间复杂度分析和空间复杂度分析。

随着信息技术的快速发展，如今空间已不再稀缺，64G,128G,256G已然平常，甚至还有1TB。但是，这是否意味着我们可以不在乎空间复杂度呢？肯定不是。

小引：摩尔定律

集成电路上可以容纳的晶体管数目在大约每经过18个月到24个月便会增加一倍。换言之，处理器的性能大约每两年翻一倍，同时价格下降为之前的一半。摩尔定律是内行人摩尔的经验之谈，汉译名为“定律”，但并非自然科学定律，它一定程度揭示了信息技术进步的速度。

2. 算法效率

如何衡量一个算法的好坏呢？

开胃小菜：

轮转数组
在这里插入图片描述

代码实现：

在这里插入图片描述

代码实现造成结果:
在这里插入图片描述

可以看见我们跑通了37个用例，但是在某一个用例时，超出了时间限制，这是什么原因导致的呢？
我们可以看看这题给出的提示
在这里插入图片描述
如果给出的数组非常大，里面存放了很多的数据，同时要轮转90次，这时就会超出时间的限制。
那么，如何衡量其好与坏呢？为此我们需要引入复杂度的概念。

复杂度概念

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。
因此衡量⼀个算法的好坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量⼀个算法的运行快慢，而空间复杂度主要衡量⼀个算法运行所需要的额外空间。

3. 时间复杂度

定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运行时间。时
间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运行时间呢？

因为程序运行时间和编译环境和运行机器的配置都有关系，比如同⼀个算法程序，用一个老编译
器运行编译和新编译器编译，在同样机器下运行时间不同。
同⼀个算法程序，用一个老低配置机器和新高配置机器，运行时间也不同。
并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

这个是我在vs编译器下realise x64位环境下，通过冒泡排序运行3次将100000排成升序各自所需要的时间，因此我们不去计算程序的运行时间。
在这里插入图片描述

那么算法的时间复杂度是⼀个函数式T(N)到底是什么呢？这个T(N)函数式计算了程序的执行次数。在编译链接过程中，我们知道算法程序被编译后生成⼆进制指令，cpu执行这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执行次数的函数式T(N)，假设每句指令执行时间基本⼀样(实际中有差别，但是微乎其微)，那么执行次数时间就是等比正相关，这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。比如解决⼀个问题的算法a程序T(N) = N，算法b程序T(N) = N^2，那么算法a的效率⼀定优于算法b。
在这里插入图片描述
实际中我们计算时间复杂度时，计算的也不是程序的精确的执行次数，精确执行次数计算起来还是很麻烦的(不同的一句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执行次数意义也不大，因为我们计算时间复杂度只是想比较算法程序的增长量级，也就是当N不断变大时T(N)的差别，上⾯我们已经看到了当N不断变大时常数和低阶项对结果的影响很小，所以我们只需要计算程序能代表增长量级的大概执行次数，复杂度的表示通常使用大O渐进表示法。

3.1 大O表示法

在这里插入图片描述

什么意思呢？
我们以上面Func1为例，T(N)=N^2+2*N+10。
根据大O阶第一条规则:只保留最高阶项,O(N)=N^2。

在这里插入图片描述

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^2)
因此：BubbleSort的时间复杂度取最
差情况为： O(N^2 )

例6

在这里插入图片描述
当n=2时，执行次数为1
当n=4时，执行次数为2
当n=16时，执行次数为4
假设执行次数为 x ，则 2x = n
因此执行次数： x = log n
因此：func5的时间复杂度取最差情况为：O(log2 n)

提问:那么log2n,logn,lgn等有区别吗？

是没有区别的，我们要注意的是增长量级,即变化的n，无论底数为多少，当n越来越大时，这个底数对结果的影响是越来越小的，当n趋于无穷时，这个影响可以忽略不计，因此上面几种表示方法都是可以的。

例7

在这里插入图片描述
调用一次Fac函数的时间复杂度为 O(1)
而在Fac函数中，存在n次递归调用Fac函数
因此：阶乘递归的时间复杂度为： O(n)

算递归的复杂度的万能公式:创建了多少次函数栈帧(递推了多少次)*单次递归执行的次数。

4. 空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运行过程中因为算法的需要额外临时开辟的空间。
空间复杂度不是程序占用了多少bytes的空间，因为常规情况每个对象大小差异不会很大，所以空间复
杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
注意：函数运行时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好
了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。