数据结构与算法介绍

数据结构与算法
发布日期:   2021-10-14
更新日期:   2021-10-16
文章字数:   4.1k
阅读时长:   15 分
阅读次数:  

1. 数据结构与算法概述

在Java中提到，程序本质上是对数据的处理，而数据需要存储在计算机中。程序除了满足基本功能外，还需要考虑性能，比如能够很快的得到计算结果，能够处理更多的数据等等。

众所周知，计算机内存是有限制的，不可能无限存储数据，因此需要对数据高效存储，对程序运行过程中的内存占用有要求；另一方面，程序也是需要考虑处理速度的，所以对数据处理方法的计算速度有要求，因此对数据存储以及对数据的计算过程需要着重考虑。

上述的内存占用和计算速度形成了两个指标：空间复杂度和时间复杂度。为了方便的存储数据以及处理数据，设计了多种不同的数据结构。简单地说，数据结构包含数据和数据之间的关系。为了更高效地处理数据，设计了多种算法，简单地说，算法就是处理的方法，解题的方法。

2. 复杂度

2.1 时间复杂度

时间复杂度是一个函数，它定性描述该算法的运行时间，或者说程序运行时间的估计值。

那么如何估计程序的运行时间呢？通常会估算算法的操作单元数量来代表程序消耗的时间，这里默认CPU的每个单元运行消耗的时间是相同的。

假设算法的问题规模为n，那么操作单元数量使用函数*f(n)来表示，随着数据规模n的扩大，**算法执行时间的增长率和f(n)的增长率相同**，这称作为算法的渐进时间复杂度，简称时间复杂度，记为O(f(n))*。

算法导论中提到：大O是用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。

输入数据的形式对程序运算时间是有很大影响的，在数据本来有序的情况下，插入排序的时间复杂度是O(n)，但如果数据是逆序的话，插入排序的时间复杂度是O(n^2)。**但是，我们一般情况下认为，大O代表的是一般情况，即一般情况下的数据形式是最常见的数据形式，考虑此时的复杂度。

数据规模对时间复杂度也有一定的影响，如下图所示：

DSAA_001.png (748×496) (gitee.io)

在决定使用哪些算法的时候，不是时间复杂度越低越好，因为简化后的时间复杂度忽略了常数项以及系数，需要考虑数据规模，如果数据规模很小，或者有常数项，O(n^2)的算法可能比O(n)的更合适。就像上图中O(5n^2) 和* O(100n)* 在n为20之前，很明显*O(5n^2)*是更优的，所花费的时间也是最少的。

那为什么在计算时间复杂度的时候要忽略常数项系数呢，也就说O(100n) 就是O(n)的时间复杂度，O(5n^2)就是O(n^2)的时间复杂度，而且要默认O(n) 优于O(n^2) 呢 ？

这里就又涉及到大O的定义，因为大O就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度，这个数据量也就是常数项系数已经不起决定性作用的数据量。

另外，我们所说的时间复杂度都是省略常数项系数的，是因为一般情况下默认数据规模足够大，基于这样的事实，给出的时间复杂度的一个排行如下所示：

1
O(1) < O(logn) < O(n) < O(n^2) < O(n^3) < O(2^n)

但是也要注意大常数，如果这个常数非常大，例如10^7，那么常数就是不得不考虑的因素了。

2.2 复杂表达式的化简

有时候我们去计算时间复杂度的时候发现不是一个简单的O(n) 或者O(n^2)， 而是一个复杂的表达式，例如：

1
O(2*n^2 + 10*n + 1000)

那这里如何描述这个算法的时间复杂度呢，一种方法就是简化法。

去掉运行时间中的加法常数项 （因为常数项并不会因为n的增大而增加计算机的操作次数）。

1
O(2*n^2 + 10*n)

去掉常数系数（上文中已经详细讲过为什么可以去掉常数项的原因）。

1
O(n^2 + n)

只保留保留最高项，去掉数量级小一级的n （因为n^2 的数据规模远大于n），最终简化为：

1
O(n^2)

2.3 O(logn)中的log是以什么为底？

其实这个底数并不重要，因为都可以转换为以另一个数为底数的对数，统一说成logn，就是为了忽略底数的描述。

DSAA_002.png (719×483) (gitee.io)

假如有两个算法的时间复杂度，分别是log以2为底n的对数和log以10为底n的对数，那么这里如果还记得高中数学的话，应该不难理解以2为底n的对数 = 以2为底10的对数 * 以10为底n的对数。

而以2为底10的对数是一个常数，在上文已经讲述了我们计算时间复杂度是忽略常数项系数的。时间复杂度的关键在于数量级。

2.4 例子

例子1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void doSome(int N){
    int example = 10;
    example *= 100;
    
    for(int i=1; i < N; i++){
        for(int j=1; j < N; j++){
            example += i;
        }
    }
    
    for(int i=1; i < N; i++){
        example -= i;
    }
    
    for(int i=1; i < N; i++){
        example += i;
    }
}

上述的时间复杂度是

1
O(2 + n^2 + n + n)

化简后是

1
O(n^2)

例子2

1
2
3
4
5
6
7
8
public void doSome(int n){
    int example = 0;
    for(int i=0; i < n; i++){
        for(int j=1; j < n; j+j*2){
            example++;
        }
    }
}

注意，时间复杂度主要看操作单元的个数，简单地认为每条Java语句就是一个操作单元，所以时间复杂度就是计算Java语句的执行次数。上面的例子中，双层循环，外循环执行n次，内循环执行次数待定。

内循环局部变量j的取值是等比数列，数列的个数就是循环的次数，只需要最后一个值小于n即可，所以k<log2(n+1)-1，即最大值是logn数量级，在加上外层循环n次，所以该程序的时间复杂度是nlogn。

2.5 递归算法的时间复杂度分析

递归算法的时间复杂度本质上是看：递归的次数*每次递归的时间复杂度。

题目：求 x 的 n 次方

这道题最直观的方法是循环， 方法1如下所示：

1
2
3
4
5
6
7
8
public void int func1(int x, int n){
    int result = 1;
    for(int i=0; i<n; i++){
        result *= x;
    }
    
    return x;
}

显而易见，该算法的时间复杂度是*O(n)*。

以递归的思路来解的话，方法2如下所示：

1
2
3
4
5
6
7
public void int func2(int x, int n){
    if(n==0){
        return 1;
    }
    
    return func2(x, n-1) * x;
}

显而易见，该递归算法的时间复杂度仍然是*O(n)*。

接下来看另一种递归算法（也可以看成是分治法），方法3如下所示：

1
2
3
4
5
6
7
8
9
10
11
public void int func3(int x, int n){
    if(n==0){
        return 1;
    }
    
    if(n%2 == 1){
        return func3(x, n/2) * func3(x, n/2) * x;
    }
    
    return func3(x, n/2) * func3(x, n/2);
}

实际上，该算法的时间复杂度也是*O(n)*。计算如下：

实际上，该算法可以的执行过程是一个二叉树，并且是满二叉树（以n为16为例），即节点的个数就是操作单元的数量。树的深度m和节点个数S的关系为S=2^(m+1) - 1，另外m=log2(n) - 1，将m带入之后，s=n-1。可以看到时间复杂度仍然和n是线性关系，即*O(n)*。

DSAA_003.png (751×430) (gitee.io)

在**func3()**的基础上，可以看到，左子树和右子树完全是一样的操作，所以计算完左子树之后，没必要再重新计算一遍右子树，直接左子树平方即可。因此，方法4如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
public int func4(int x, int n){
    if(n==0){
        return 0;
    }
    
    int left = func4(x, n/2);
    if(n % 2 == 1){
        return left * left * x;
    }
    
    return left * left;
}

不难发现，该算法的操作单元数量其实就是二叉树的深度，即log2(n)-1，即算法复杂度是*O(logn)*。

2.6 空间复杂度

时间复杂度指的是程序执行的时间长短，那么空间复杂度指的是什么呢？空间复杂度是对一个算法在运行过程中占用内存空间大小的量度。利用程序的空间复杂度，可以对程序运行中需要多个内存有个预先估计。

以下两个问题需要特别注意：

  1. 空间复杂度是考虑程序（可执行文件）的大小吗？

    很多人都会混淆程序运行时内存大小和程序本身的大小，这里强调一下，空间复杂度是考虑程序运行时占用内存的大小，而不是可执行文件的大小。

  2. 空间复杂度是准确算出程序运行时所占用的内存吗？

    空间复杂度仅仅是对内存占用的预估，并不是实际值，而且除了程序本身，还有很多因素会影响程序真正内存的使用大小，例如编译器的内存对其，编程语言容器的底层实现等等这些都会影响到程序内存的开销。

和时间复杂度不同，时间复杂度是将操作单元作为一个时间单元，而空间复杂度则是将变量作为空间单元。

例子1如下所示：

1
2
3
4
int j = 0;
for(int i=0; i< n; i++){
    j++;
}

这段代码随着n的变化，对内存的占用并不会变化，所以此算法的空间复杂度为一个常量，表示为*O(1)*。

例子2如下所示：

1
2
3
4
int[] j = new int[n];
for(int i=0; i<n; i++){
    j[i] = 1;
}

这段代码则随着n的变化，内存开销保持线性增长，即数组随着n的变化会开辟不同长度的内存空间，空间复杂度为*O(n)*。

2.7 斐波那契数列复杂度分析

斐波那契数列：0，1，1，2，3，5，8，…

第一项是0，第二项是1，之后的项是前面两项之和。斐波那契数列一般是求前n项和或者求第n项。下面以求解第n项为例。

从斐波那契数列的描述很容易想到最简单的递归算法，方法1如下所示：

1
2
3
4
5
6
7
8
9
10
11
public int fibonacci(int n){
    if(n<=0){
        return 0;
    }
    
    if(n==1){
        return 1;
    }
    
    return fibonacci(n-1) + finobacci(n-2);
}

这段代码逻辑比较清晰，代码比较简洁，分析一下时间复杂度。每次递归的时间复杂度为O(1)，主要还是看递归次数。以二叉树的形式来分析递归过程，每个节点表示递归一次，求解递归次数就是求解二叉树的节点个数。

DSAA_004.png (765×577) (gitee.io)

可以看到每次递归，一定要需要前一项，那么其二叉树的深度就是n，那么深度为n的二叉树的节点个数最多为2^n-1，所以递归次数为2^n-1，该算法的时间复杂度为*O(2^n)*，耗时还是挺大的。

从图中可以看出，很多项都被重复计算了，完全可以有优化一下，减少递归次数，即保存一些项，方法2如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int fibonacci(int first, int second, int n){
    if(n <= 0){
        return 0;
    }
    
    if(n < 3){
        return 1;
    }
    
    else if(n == 3){
        return first + second;
    }
    
    else{
        return fibonacci(second, first + second, n-1);
    }
}

该算法和非递归算法的逻辑很像，从前两项开始计算，直到计算到指定项。只不过该算法的是用递归来控制项数（或者认为将前面两项相加，n作为剩余的项数），所以该算法的时间复杂度和空间复杂度均为*O(n)*。

非递归方法如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int fibonacci3(int n){
        int first = 0;
        int second = 1;
        int temp;

        if(n == 1){
            return 0;
        }

        else if(n == 2){
            return 1;
        }

        else{
            for(int i=3; i<= n; i++){
                temp = second;
                second += first;
                first = temp;
            }

            return second;
        }
}

非递归算法的时间复杂度为*O(n)，空间复杂度为O(1)*。

和时间复杂度一样，递归算法的空间复杂度=每次递归的空间复杂度*递归深度。因为每次递归所需的空间都被压到调用栈里（这是内存管理里面的数据结构，和算法里的栈原理是一样的），一次递归结束，这个栈就是就是把本次递归的数据弹出去。所以这个栈最大的长度就是递归的深度。此时可以分析这段递归的空间复杂度，从代码中可以看出每次递归所需要的空间大小都是一样的，所以每次递归中需要的空间是一个常量，并不会随着n的变化而变化，每次递归的空间复杂度就是O(1)。

2.8 二分查找（递归实现）复杂度分析

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int binarySearch(int[] arr, int l, int r, int goal){

        int mid = (l + r) / 2;

        if(l > r){
            return -1;
        }

        if(arr[mid] == goal){
            return mid;
        }

        else if(arr[mid] < goal){
            return binarySearch(arr, mid + 1, r, goal);
        }
        return binarySearch(arr, l, mid, goal);
    }
}

可以看到，二分查找的过程和二叉树一样，最坏情况下操作单元的数量为树的深度，即时间复杂度是*O(logn)*。

*另外，传递数组实际上是传递的数组首元素的地址，即每次递归的空间复杂度是O(1)，而递归次数是logn，所以空间复杂度是O(logn)。*

2.8 内存对齐（待补充…）

3. 数据结构

有了上面的几个指标之后，为了更好地存取数据，设计了多种不同的数据结构。从元素之间的关系上来说，数据结构分为线性数据结构和非线性数据结构。

  • 线性数据结构

    存在唯一的一个“第一个元素”，存在唯一的一个“最后一个元素”，除了第一个元素之外，其他数据元素均有唯一的“前驱元素”，除了最后一个元素之外，其他数据元素均有唯一的“后继元素”。简单地说，有首尾元素，除了二者，其余元素均和两个元素相邻。

  • 非线性数据结构

    和线性数据结构对比，可能没有首尾元素的概念，也不一定只有前后两个元素相邻，可能存在多个邻居元素，并且可能没有前驱和后继的概念。

针对两类数据结构，设计了八种基本数据结构，如下所示：

基本数据结构 类型
数组 线性
队列 线性
栈 线性
链表 线性
树 非线性
散列表 非线性
堆 非线性
图 非线性

当然这只是最基本的数据结构，这些结构还可以变形。

4. 算法

算法则是解决问题的方法，和高中数学一样，对于某类问题，有着特定的解题思路。那么对于计算机处理数据来说，同样如此。对于不同的数据结构以及数据之间关系，解决问题的方法也不一样。算法主要考虑最优的解题方法，这里的最优可能是空间复杂度，也可能是时间复杂度。

典型的算法有回溯法、贪心法、分治法、动态规范法等等。。。

5. 备注

部分参考代码随想录 (programmercarl.com)。

文章作者: 浮云
文章链接: https://ihianian.github.io/2021/10/14/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E4%BB%8B%E7%BB%8D/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
数据结构与算法
赏
  目录