数据结构——算法的复杂度分析

前言

这一节是对绪论的补充。复杂度的分析，在很多的OJ比赛中的作用很大，我们往往在做题前会事前估计和事后估计，但是一般都是事前估计。考研的人er这一块一定要掌握。算法的复杂度的分析还需要你们自己线下去进行学习。看完我的数据结构课程希望能对在数据结构学习的过程迷茫的同学带来帮助！！！

analysis of algorithms

很多人可能会用algorithms complexity analysis 算法复杂度分析（知道即可）

在这应该是用analysis of algorithms的概念

我们都常说一句话：条条大路通罗马，在去罗马的过程我们会有不同的道路，会有不同的交通工具。在自行车、步行和飞机的选择中，不同的道路到达的时间和用的资源不同带来不同的结果，于是我们提出了复杂度的概念。

有限的资源下我们要控制时间，复杂度的分析就是为了能够选出最优的解。

(1)对于时间的分析 我们叫做时间复杂度

(2)对于资源的分析 我们叫做空间复杂度

我们就是分析一条路最高效的，而这条路就是数据结构和算法。

很浅显易懂的概念。而对于时间复杂度我们用大O来进行标记。

Big O复杂度标记符以及举例

假如有个数组：arr=[1,2,3,4,6,7,12313];之前说过数据结构就是对数组进行CRUD分析。

因为arr[0]=1,就相当于我们现在要查一个数就是1。

(0)查单个元素的值：O(1) ：1就是时间T

(1)那假如说我现在要查n个数字，不就是O(N)啰，即遍历这个数组。

(2)假如现在我们的图copy了一份然后，每一个数都跟另一个表的数配对一遍，就是O(N^2)。还不是一一匹配，而是一个数字和另一张图的每一个数匹配。

这些知识点很重要，一定要记住。

复杂度比较函数图

在这我们要列出不同的复杂度，递归的案例就是阶乘所以时间复杂度很高。

对数的复习

照顾一下数学不好的同学。

2³=8 2^?=8

x=b^y y=log_bx

那log₂16=4；

这玩意有什么作用呢？

[1,2,3]是一个静态数组，当我们想要扩容时，我们只能重新增加一倍，即乘以2。每次扩容一被就是指数加1

第二个例子：我们现在要找一个人，即折半查找

每次都是折一半，效率越高，折半查找的复杂度就是log₂(N)。

看上图知，数越大的时候，越稳定