【数据结构】初识数据结构与复杂度总结

前言

C语言这块算是总结完了，那从本篇开始就是步入一个新的大章——数据结构，这篇我们先来认识一下数据结构有关知识，以及复杂度的相关知识

个人主页：小张同学zkf

若有问题评论区见

感兴趣就关注一下吧

1.什么是数据结构

2.什么是算法？

3.算法的复杂度

3.1时间复杂度

3.2三种情况

3.3空间复杂度

1.什么是数据结构

数据结构是计算机存储，组织数据的方式，指的是相互之间存在一种或多种特定关系的数据元素的集合

2.什么是算法？

数据结构离不开算法，那算法是什么东西那，简单来说是一个定义好的计算过程。就是取一个或一组值输入，并产生出一个或一组值作为输出，当中产生的的计算步骤，用来将输入数据转化成输出结果

3.算法的复杂度

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

时间复杂度主要衡量一个算法的快慢，而空间复杂度主要衡量一个算法运行的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎，但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度，所以我们如今已经不需要在特别关注一个算法的空间复杂度。

3.1时间复杂度

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数（注：这里的函数是数学上的函数，不是c语言的函数！！！），它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序跑起来，才能知道，但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方法。一个算法所花费的的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度

即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

//请计算一下Func1中++count语句总共执行了多少次?
void Funcl(int N)
{
int count =0;
for(int i=0;i<N;++i)
{
for(int j=0;j<N;++j)
{
++count;
}
}

for (int k=0;k<2*N;++k)
{
++count;
}
int M=10;
while(M--)
{
++count;
}
printf("%d\n",count);
}

上面的时间复杂度是多少

我们用数学函数来表示，来看第一个函数，两个for循环，那执行次数是不是就是N的平方次，再看第二个函数执行2N次，最后一个函数执行10次

那就是F（N）=N^2+2*N+10

精算值估算值

N=10 F(N)=130 100

N=100 F(N)=10210 10000

N=1000 F(N)=1002010 1000000

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法

那么要求大概值，哪个表达式对次数影响最大呢，是不是N^2 最大，我么可以这样想一下，如果N越来越大，后面俩表达式2*N和10是不是对时间复杂度影响越来越小，我们取极限，那后面俩就没影响，只有N^2对次数影响特别大，所以只保留这一项，我们也可以从这里看出来，若为多项式，我们只取次数高的那一项

那么这个函数的时间复杂度为O（N^2） 这也就是大O的渐进表示法

那我们再来看一个例子，巩固一下

//计算Func3的时间复杂度?
void Func3(int N,int M)
{
int count =0;
for (int k=0;k<M;++k)
{
++count;
}
}
for (int k=0;k<N;++k)
{
++count;
}
printf("%d\n",count);

我们还是先用函数表示 F（N）=N+M

这下就有疑问了，那这个用大O怎么表示

我们可以看一下，这里没有明确说明N远大于M还是M远大于N，都没有明确说明，那就是对执行次数影响是同等的，谁都不能舍去，所以结果为O（N）=N+M

我们再来看一个

//计算Func4的时间复杂度?
void Func4(int N)
{
int count =0;
for (int k =0;k<100;++k)
{
++count;
}
printf("%d\n",count);
}

这个时间复杂度又是多少呢

我们乍一看这次执行次数可以直接看出来，一共执行了100次

那大O怎么表示那，其实在大O里常数全部用1来表示，所以结果为O（N）=1

一定要注意这里，这里的结果1不是执行了一次，而是代表常数次，就是我们可以看出来的次数，执行次数不是未知数的话，那运行时间就是固定的，所以它们的时间复杂度都是O（N）=1！！！！！！！

综上，我们可得出推导大O的方法

1.用常数1取代运行时间中的所有加法常数

2.在修改后的运行次数函数中，只保留最高阶项，如果最高阶项存在且不是1，则去除与这个项目相乘的常数（也就是把系数去掉）

3.O（1）不是代表1次，是代表常数次

3.2三种情况

有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

我们来看一下这个函数，是不是有点眼熟，没错我们之前总结过的冒泡排序，那它的时间复杂度该怎么求那，我们要求它的最坏情况，我们先想一想，冒泡排序是怎么排序的，是不是第一个数先进行挨个比较，然后是第二个数字，以此类推，那我们第一个数字是不是要比较N-1次，第二个数字就是N-2次……直到最后比较一次，那把这些都加起来是不是就是我们的时间复杂度了，那就是求等差数列的和，函数为N*(N-1)/2,大O表示法取最高项结果为O（N^2）

我们继续看一个

这个是不是也是有点眼熟，对我之前总结的猜数字游戏里的二分查找，那它的时间复杂度是多少那，我们先来想一想这个函数怎么实现的，是每次查找缩小一半范围，相当于除2，查找一次除一次2，那N次就是除N个2，那时间复杂度不就是除2的次数嘛，那不就是log2N嘛，用大O表示就是O(N)=log2N

我们再来看一个

还记得这个吧，没错这个也是我之前总结的递归问题中的青蛙跳台阶——斐波那契数列，这个时间复杂度又是什么那

我们看一下这个函数，是不是递归一次执行一次，但它一个函数内递归了两次，那它接下来是不是像树状线一样，一个函数分两个函数，如图所示，我们来找一下规律，是不是从2^0到2^（n-2）

那把这些都加起来，就是时间复杂度了

我们可以根据错位相减法得到2^（n-1）-1,用大O表示就是O（N）=2^N

3.3空间复杂度

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

这个空间复杂度是多少

我们来看一下，这个函数开辟了一个数组空间，以及一些变量的空间，都是常数个，所以用大O表示是O（N）=1

继续看一个

这个空间复杂度是多少

这里函数运行时额外开了一个n+1的空间，这个空间就是它的空间复杂度用大O表示就是O（N）

再看一个递归

这个空间复杂度是多少

它运行时创立了N个函数栈帧，所以它的结果为O（N）

我们来看一个复杂点的

这个时间复杂度我们知道了是O（2^N）空间复杂度那

这个我们要好好想想，递归函数在创建函数栈帧的特点，第一列的函数栈帧创建完，调用完再销毁，后几列的函数递归再用第一列的曾经函数栈帧所用的空间，不会额外再开辟新的函数栈帧，简单来说就是第一列函数递归的深度就是它的空间复杂度，后面的函数递归，在第一列函数栈帧用完销毁的空间基础上，再重复利用这个空间进行第二次函数递归