数据结构之基本概念

Myth丶恋晨 2022-12-25 13:57 216阅读 0赞

### 目录 ###

*  1.什么是数据结构
 *  2.什么是算法
 *  3.时间复杂度与空间复杂度
 *  4.时间复杂度的计算
 *  5.最大子列和应用实例

# 1.什么是数据结构 #

**首先对于数据结构没有一个统一的定义，其实不用去记那些空洞定义**，从一个例子出发：如何在书架上摆书？  
第一种方式随便放，这样新书插入比较容易，但是查询某个图书比较困难。  
第二种方式，按照图书字母顺序摆放，插入与查找可以通过二分查找。  
第三种方式就是把书架分为几块区域，每块区域指定某种类别的图书，每个类别下，按照书名的拼音字母顺序摆放，插入与查找时，先定类别，再二分查找。这种方式也有个问题：类别分多细？可以看出书架摆书这个问题其实是非常复杂的。

经过这个问题，我们可以看出来**解决某个问题的效率，跟数据的组织方式相关**。

另一个例子：一个打印从1到N的正整数的例子，该例子有两种实现方式：分别为循环实现与递归实现。  
循环实现：

void PrintN ( int N )
    {  int i;
    for ( i=1; i<=N; i++ ){ 
    printf(“%d\n”, i );
    }
    return;
    }

递归实现：

void PrintN ( int N )
    {  if ( N ){ 
    PrintN( N – 1 );
    printf(“%d\n”, N );
    }
    return;
    }

传入100000，递归实现的结果如下：  
![在这里插入图片描述][20201202214107887.png]  
当分别对这两个函数传入100000后，从打印结果可以看出，递归实现的方式，会出现非正常中断的现象，这是因为空间复杂度过高导致的堆栈溢出（具体参见[函数的递归调用][Link 1]这篇博客）。  
经过这个例子可以看出**解决问题方法的效率和空间的利用率有关**。

第三个例子：计算给定多项式在给定x处的值  
![在这里插入图片描述][20201202213006137.png]  
两种实现方式：  
第一种：直接实现

double f( int n, double a[], double x )
    {  int i;
    double p = a[0];
    for ( i=1; i<=n; i++ )
    p += (a[i] * pow(x, i));
    return p;
    }

第二种，对于这个式子，进一步可以简化为下式  
![在这里插入图片描述][20201202213159110.png]  
也就是秦九韶算法

double f( int n, double a[], double x )
    {  int i;
    double p = a[n];
    for ( i=n; i>0; i-- )
    p = a[i-1] + x*p;
    return p;
    }

经过对比这两个算法在计算给定多项式 f ( x ) = ∑ i = 0 9 i ⋅ x i f(x)=\\sum\_\{i=0\}^9\{i\\cdot x^i\} f(x)=∑i=09i⋅xi在给定点x = 1.1 处的值f(1.1)所花费的时间看出第二种实现方式的算法所花时间较第一种方式少了一个量级。此例子的源码可参考我的这篇博客[clock()计时操作（包含函数指针的应用）][clock]

经过这个例子又可以看出**解决问题方法的效率，和算法的巧妙程度有关**。

经过上述三个例子，我们可以得到关于什么是数据结构的结论：

*  数据对象在计算机中的组织方式，这包括逻辑结构与物理存储结构。（图书摆放的方式）
 *  数据对象必定与一系列加在其上的操作相关联 。（查找和插入图书）
 *  完成这些操作所用的方法就是算法。

经过上述已了解什么是数据结构，下面介绍什么是**抽象数据类型**？

字面可以看到两个关键词，一个是抽象、一个是数据类型：  
**数据类型**：数据对象集（所有图书），数据集合相关联的操作集（查找和插入图书）  
**抽象**：描述数据类型的方法不依赖于具体实现：与数据存放的机器无关；与数据存储的物理结构无关；与实现操作的算法和编程语言无关。  
简单总结下就是抽象数据类型只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题。抽象数据类型对应于编程语言中的数据类型。

--------------------

# 2.什么是算法 #

算法的定义较数据结构而言比较简单，其定义如下：

*  一个有限指令集
 *  接受一些输入（有些情况下不需要输入）
 *  产生输出
 *  一定在有限步骤之后终止
 *  每条指令必须
    
     *  有充分明确的目标，不可以有歧义
     *  计算机能处理的范围之内
     *  描述应不依赖于任何一种计算机语言以及具体的实现手段

可以看出算法是一种在有限步骤后终止的指令集，它在一定程度上抽象（伪代码），不依赖于具体的实现。

--------------------

# 3.时间复杂度与空间复杂度 #

如何评价算法的好坏，一般有空间复杂度和时间复杂度两种指标：

**空间复杂度  S ( n ) S(n) S(n)**——根据算法写成的程序在执行时**占用存储单元的长度**。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。

> 扩展一下：一个上机的程序处理需要存储空间来寄存本身所用的指令、常数、变量、输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。如果输入数据所占空间只取决于问题本身和算法无关，则只需要分析输入和程序之外的额外空间，否则应同时考虑输入本身所需空间（和输入数据的表示形式有关）。若额外空间相对于输入数据量来说是常数，则称此算法为**原地工作**。这也就是就地算法。

**时间复杂度  T ( n ) T(n) T(n)**——根据算法写成的程序在执行时**耗费时间的长度**。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。**对于其中的n指的是问题的规模**。

对于上面的第二个关于输出N个整数的例子，递归实现的方式，每递归一次需要额外的空间去辅助完成，所以递归实现的算法的空间复杂度为 S ( N ) = N S(N) = N S(N)=N，而循环实现的空间复杂度为 S ( N ) = 1 S(N) = 1 S(N)=1

对于上面的第三个关于多项式计算的例子，普通实现的方式为什么要比秦九韶算法的要复杂，可以从下面的角度出发，机器运行加减法的速度要比乘除法快很多，所以可以通过比较函数做了多少次乘除法（加减法忽略不计）。普通实现的做了 ( n 2 + n ) / 2 (n^2 +n)/2 (n2\+n)/2次乘法（注意pow(x,i)进行i-1次乘法），而秦九韶算法做了n次乘法。所以后者比较简单，运行时间比较短。  
需要注意：实际时间复杂度并不是单单比较乘除法的次数，而是更多的比较基本操作（固有数据类型的操作，这包括加减乘除）重复执行的次数，也就是说，循环体内执行的可以是加减乘除中的任何一个或者其结合体这都算进行了一次基本操作，不过对于引入的一些函数需要去额外计算其基本操作重复执行的次数，如pow，故上述两种方式的时间复杂度分别为 O ( n 2 ) 与 O ( n ) O(n^2)与O(n) O(n2)与O(n)。

我们常看到的时间复杂度实际上指的是最坏情况复杂度，而不是平均复杂度，主要原因在于平均复杂度很多情况下不容易求取。  
下图为常见的几种输入规模n与函数f的关系以及随着问题规模的增大与计算机计算所需时间的关系：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 1]  
可以看出随着问题的规模增大，不同的f所需时间相差很大，所以需要尽可能的去设计时间复杂度较小的算法。（此处若想去验证 2 100 2^\{100\} 2100看看计算时间是不是很长，需要注意溢出问题，对于c语言int型最大值要比 2 100 2^\{100\} 2100小,会造成溢出 ）  
注：一般计算机的运算速度可以达到每秒上百万条指令

# 4.时间复杂度的计算 #

*  for循环的时间复杂度等于循环次数乘循环体代码的复杂度
    
     *  对于循环体中是递归程序的，可以利用\*\*[分治法的主定理][Link 2]\*\*去计算时间复杂度
 *  if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中最大 。

--------------------

# 5.最大子列和应用实例 #

给定N个整数的序列 A 1 , A 2 , … , A N \{ A\_1, A\_2, …, A\_N\} A1,A2,…,AN，求函数 f ( i , j ) = m a x \{ 0 , ∑ k = i j A k \} f(i,j) = max \\\{0,\\sum\_\{k=i\}^jA\_k\\\} f(i,j)=max\{ 0,∑k=ijAk\}的最大值。

> 对应力扣053最大子序和： 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例:  
> 输入: \[-2,1,-3,4,-1,2,1,-5,4\] 输出: 6 解释: 连续子数组 \[4,-1,2,1\] 的和最大为 6。  
> 链接：https://leetcode-cn.com/problems/maximum-subarray

> 命名规范问题：关于c语言的命名规范问题，对于c语言，一般而言**变量**命名采用驼峰规则，若变量采用多个单词拼成，首单词首字母小写，其余单词的首字母大写。对于**函数**，为了区分库函数与自己定义的函数，故自己定义的函数一般采用首字母大写。**宏定义**里面的变量全大写。

**算法1**：暴力求解

int MaxubseqSum1(int *A, int N)
    { 
        int ThisSum, MaxSum = A[0];
        int i, j, k;
        for(i = 0; i < N; i++){  //i是子列左端位置
            for(j = i; j < N; j++){  //j是子列右端位置
                ThisSum = 0; //ThisSum是从A[i]至A[j]的子列和
                for(k = i; k <= j; k++) 
                    ThisSum += A[k];
                if(ThisSum > MaxSum) //如果刚得到的这个子列和更大
                    MaxSum = ThisSum; //更新结果
            }
        }
        return MaxSum;
    }

该算法的时间复杂度为 O ( n 3 ) O(n^3) O(n3).

**算法2**：进一步优化  
对于上述暴力求解，可以发现，第三层循环求子列和的时候，都是从i处开始计算到j处的子列和，接下来是从i处计算到j+1处，实际上我们不必每次从i开始，而从上一次得到的结果往后加一项就行，所以第三层循环没必要。

int MaxsubseqSum2(int *a, int n)
    { 
        int i, j, k;
        int thisSum, maxSum = a[0];
        for(i = 0; i < n; i++){ 
            thisSum = 0;
            for(j = i; j < n; j++){ 
                thisSum += a[j];
                if(thisSum > maxSum)
                    maxSum = thisSum;
            }
        }
        return maxSum;
    }

该算法的时间复杂度： O ( n 2 ) O(n^2) O(n2)

**算法3**：分而治之  
对于时间复杂度为 O ( n 2 ) O(n^2) O(n2)的算法，我们希望对其加以改进使其复杂度达到 O ( n l o g n ) O(nlogn) O(nlogn)

> 分而治之也就是分治法，什么是分治法？如果我们有一个很复杂的大问题，很难直接解决它，但是我们发现可以把问题划分成子问题，如果子问题规模还是太大，并且它还可以继续划分，那就继续划分下去。直到这些子问题的规模已经很容易解决了，那么就把所有的子问题都解决，最后把所有的子问题合并，我们就得到复杂大问题的答案了。

对于该问题，我们可以将整个序列一分为二，递归的去解决左右两边的问题，分别求左半部分的最大子列和，右半部分的最大子列和。然后再去求横跨左右两部分的最大子列和，那么整体的最大子列和一定在三者之中产生。也就是三个子问题都能解决，那么答案就是三个结果的最大值。所以这就是先分，后治。

如下图所示：  
![在这里插入图片描述][20201204152137771.png]  
分析算法复杂度， T ( N ) = 2 T ( N / 2 ) + c N T(N) = 2T(N/2) + cN T(N)=2T(N/2)\+cN，因为一分为2，解决每半部分的时间复杂度为T(N/2),因为规模减半了，而计算横跨左右两半部分的最大子列和时扫描一次整个序列，故其复杂度为O(N).

因此其递推公式为：  
 T ( N ) = 2 T ( N / 2 ) + c N T(N) = 2T(N/2) + cN T(N)=2T(N/2)\+cN  
=  2 \[ 2 T ( N / 2 2 ) + c N / 2 \] + c N 2\[2T(N/2^2)+cN/2\]+cN 2\[2T(N/22)\+cN/2\]\+cN 当N/2^k = 1时，此时有T(1)=O(1)  
=  2 k O ( 1 ) + c k N 2^kO(1)+ckN 2kO(1)\+ckN 把N/2^k = 1代入  
= O ( N l o g N ) O(NlogN) O(NlogN)  
因此其时间复杂度为 O ( N l o g N ) O(NlogN) O(NlogN)

int Max(int a, int b, int c)
    { 
        return a > (b > c ? b : c) ? a : (b > c ? b : c);
    }
    int MaxSubseq(int *a, int left, int right)
    { 
        if(left == right)
            return a[left];
        int center = (left + right)/2;
        /* 分别找到左右最大子列和*/
        int leftSum = MaxSubseq(a, left, center);
        int rightSum = MaxSubseq(a, center + 1, right);
        /* 找到横跨左右两半部分的最大子列和*/
        int maxLeftBorderSum = a[center];
        int leftBorderSum = 0;
        for(int i = center; i >= left; i--){ 
            leftBorderSum += a[i];
            if(leftBorderSum > maxLeftBorderSum)
                maxLeftBorderSum = leftBorderSum;
        }
        int maxRightBorderSum = a[center + 1];
        int rightBorderSum = 0;
        for(int i = center + 1; i <= right; i++){ 
            rightBorderSum += a[i];
            if(rightBorderSum > maxRightBorderSum)
                maxRightBorderSum = rightBorderSum;
        }
        return Max(leftSum, rightSum, maxLeftBorderSum+maxRightBorderSum);
    }
    
    int MaxsubseqSum3(int *a, int n)
    { 
        return MaxSubseq(a, 0, n-1);
    
    }

另外需要注意的是，编程过程中判断相等的时候，可以将常数放在前面，防止由于书写错误而引起的错误，比如1=len，书写的时候少写了一个等号，而len=1就认为是赋值操作，没有问题，但是1=len就会报错了。

算法4：在线处理

> 在线处理，在线的意思是指每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都能正确给出当前的解。

int MaxsubseqSum4(int *a, int n)
    { 
        int thisSum = 0,maxSum = a[0];
        for(int i=0; i < n; i++){ 
            thisSum += a[i]; //向右累加
            if(thisSum > maxSum) //发现更大的和更新结果
                maxSum = thisSum;
            if(thisSum < 0) //如果为负数,则不能使后面的结果增大,放弃前面的和
                thisSum = 0;
    
        }
        return maxSum;
    }

经过上述理解，写出一个好的算法真的不是很容易，需要有数学基础、逻辑能力以及对一些常用方法的熟练掌握。

[20201202214107887.png]: /images/20221120/95e5114abd6d45a798f629e5c6664960.png
[Link 1]: https://blog.csdn.net/qq_38048756/article/details/110475125
[20201202213006137.png]: /images/20221120/ffefc431f8b54c52a5fc511f38d123e1.png
[20201202213159110.png]: https://img-blog.csdnimg.cn/20201202213159110.png
[clock]: https://blog.csdn.net/qq_38048756/article/details/102613004
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201203145902639.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201203150632348.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2,size_16,color_FFFFFF,t_70
[Link 2]: https://blog.csdn.net/q547550831/article/details/51533887
[20201204152137771.png]: https://img-blog.csdnimg.cn/20201204152137771.png