数据结构与算法

数据结构与算法概述

2018-09-12  本文已影响33人  大大纸飞机

初衷

学习数据结构与算法的知识，并没有一个完备的理由。如果是作为一名算法工程师，这无可厚非，但对于我们大部分的开发者而言，算法对工作的影响甚微，甚至可能不需要任何算法就可以完成全部的工作。那么，我们为什么要学习数据结构与算法？我总结有以下几点：

首先，算法是面试的常客。很多人会抱怨面试为何要问算法，工作中又用不到，调侃是面试造火箭，工作拧螺丝。但不可否认的是，算法可以排除一些滥竽充数的人。算法可以考察一个人的逻辑思维，应变力，也可以考察出现困难时的解决能力。所以，单从这个层面，我们应该学习算法。

其次，从个人发展而言，算法能够助我们突破瓶颈。随着工作年限的增加，我们做的工作也会从编程向优化倾斜，届时提高响应速度，解决系统瓶颈也会成为工作的主要内容之一。所以，如果要成为一名高级工程师，让自己在步入中年时不被淘汰，我们应该学习算法。

除此以外，还有一点原因十分重要。计算机技术飞速发展，各种新的语言、新的框架、新的思想层出不穷，铺天盖地的新技术没有人能够完全掌握。然而它们都可能不会长久，在不久后就会被更新的技术取代，也就意味着我们依托于此的积累都不复存在，（当然这部分知识也极为重要，不过我们应该分出一部分精力研究一些基础理论知识）。但一些基础的理论不会被淹没，诸如计算机原理、操作系统原理、算法等，这些是计算机技术的基石。我们应该掌握不变的，以不变应万变，以免陷入吾生也有涯，而知也无涯。以有涯随无涯，殆已！的窘境。

既然选择了学习算法，首先要对一些基本概念有所认知。接下来的这些基本知识点，是我们每个人都必须深刻理解的，只有知道何为算法，为何需要算法，才能体会到学习算法的意义。

基础知识

计算机的存储结构

数据千变万化，但被加载到内存中的方式只有两种：顺序和链式。数据通常不是独立的，除数据本身外还有它和其他数据之间的关系，计算机能够表示数据和这种关系的方式只有这两种，它们的区别主要在于关系的表示上。

① 顺序存储结构

是指将数据存放在连续的存储单元中，通过相对位置来表示数据间关系，数组就是这一方式的典型实现。它在内存中结构示意图如下：

顺序存储示意图

② 链式存储结构

是指数据存放在任意的内存单元中，并为数据增加一个指针域，指向它的下一个（或上一个）元素的地址，以此来建立关系，我们使用的链表就是这一方式的典型实现。它在内存中结构示意图如下：

链式存储示意图

数据逻辑结构

数据之间同样都有联系，这种关系就是逻辑结构。通常有以下四类：

1. 集合

指数据同属于一个集合，除此以外没有任何关系，这种关系很弱，不是研究的重点。示意图如下：

集合示意图

2. 线性结构

是指数据之间是一对一的关系，例如数组和链表都是一对一的结构，示意图如下：

线性结构示意图

3. 树形结构

是指数据之间存在一对多的关系，例如二叉树就是这种结构，示意图如下：

树形结构示意图

4. 图形结构

是指数据之间存在多对多的关系，示意图如下：

图形结构示意图

算法定义

为了快速高效的把数据加载到计算机内存中，算法应运而生。它的定义如下：

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

算法的特性

1. 输入输出

算法至少有零个或多个输入，至少有一个输出。一些特定的算法可以没有输入，但是算法必须有输出。

2. 有穷性

算法必须在执行有限步数之后结束，且每一步都必须在有穷时间内完成。

3. 确定性

算法的每一步都必须有确切唯一的含义，且对于相同的输入，必须产生相同的输出结果。

4. 可行性

算法必须是可以实现的，能够实际使用。理论上可以实现但现实上无法完成的算法不包括在内，这部分知识我们不进行研究。

算法的衡量标准

要设计一个可以使用的算法不难，但是算法也有优劣，衡量一个算法的好坏有以下几个标准：

1. 正确性

算法的正确性，分为以下几个层面：

一般而言，满足前3点的算法都是合格的。

2. 可读性

算法必须对人友好，难以理解的算法不实用，容易出错而且难以发现问题。

3. 健壮性

也就是鲁棒性，算法必须能够处理各种错误的情况，并给出合理的解决方式。

4. 效率高存储量低

算法的执行时间越短，占据存储的大小越小，算法就越好。

时间复杂度

影响算法运行时间的因素有很多，例如计算机的运算能力、编写算法使用的语言、算法的规模等。其中除了算法规模以外其他都与实际环境相关，所以主要衡量算法规模对时间的影响。算法的时间复杂度用T(n) = O(f(n))表示，也就是大O记法。其中n是数据的规模，意思是时间复杂度是规模的函数。

下面举几个例子说明这个函数的推导方法：

1. 常数阶

int a = 10, b = 20;
System.out.println("sum of a and b is :" + (a+b));

像这种与规模无关的代码，其时间复杂度都是O(1)。因为无论a或者b多大，计算机都只需要执行以上两行代码即可。

2. 线性阶

int sum = 0;
for(int i=0, len = 100; i<len; i++){
    sum += i;
}

当len的值不同时，for循环内部的代码需要执行的次数也不同，可以看到它需要执行len次，所以时间复杂度是O(n)。

3. 对数阶

int n = 100;
int count = 1;
while(count < n){
    count *= 2;
}

以上代码while循环部分也和n有关，但是它的执行次数并不是n次，可以看到count的值每次都乘2，也就是执行一定次数的乘2操作后，循环终止。相应的求解公式为2x = n，可以得到x = log2n。通常省略下标，也就是时间复杂度为O(logn)。

4. 次方阶

int n = 100;
for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        // 复杂度为O(1)的操作
    }
}

像这种双重for循环，其执行次数为n×n，所以时间复杂度为O(n2)。再看下面的代码时间复杂度是多少呢？

int n = 100;
for(int i=0; i<n; i++){
    for(int j=i; j<n; j++){
        // 复杂度为O(1)的操作
    }
}

这里仅是把j的起点从0换成了i。可以看到，当i=0时，j执行了n次；当i=1时，j执行了n-1次；...；当i=n-1时，j执行了1次。所以总的执行次数为：

n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = n2/2 + n/2。

从数学的角度来看，当n越大时，n/2对函数增长的影响越小，所以我们只需要关心n的最高阶即可，以上的时间复杂度依然是O(n2)。

5. 总结

通过以上几个实例，可以发现，时间复杂度并不是精确计算算法执行的时间，而是根据数据规模的一种估算，且仅考虑最重要的因素：n的最高阶。

在说时间复杂度时，通常有两个不同的概念：最坏时间复杂度和平均时间复杂度。比如要从一个数组中查询一个值，如果这个值就在第一位，那么只需要一次就找到了。如果这个数字在最后一位，则必须对数组进行遍历，需要执行n次操作。这里前者就是最好时间复杂度，为O(1)，后者就是最坏时间复杂度，为O(n)。平均时间复杂度则是指对所有可能情况需要的时间的均值，以上操作的平均时间复杂度为O(n/2)。

很明显，平均时间复杂度更接近实际，但是实际中遇到的问题都远比上述例子复杂的多，它的平均时间复杂度很难计算，所以我们一般采用最坏时间复杂度来衡量算法的效率。

空间复杂度

是指算法运行时需要的存储空间的大小。这里的存储空间大小不包括代码本身、输入数据本身等所占据的空间，而是指为了实现算法所额外占用的空间，也就是和算法相关的那部分。比如为了实现算法，需要额外创建一个数组，来进行中转。算法的空间复杂度也是规模n的函数。

总结

有关数据结构和算法的基础知识就是这些，数据结构和算法的目的就是寻找高效的方式让计算机处理问题。相关的知识涉及到线性表、树、图等数据结构，还包括串、排序、查找、动态规划等内容。本系列文章会按照以下顺序对这些知识一一梳理：

总结完基础知识后，还会对每个模块的经典题目进行练习。学会了数据结构，等于是掌握了九九乘法表，而进行算法题目的练习，就相当于使用九九乘法表解决实际问题。只有两者兼顾，才能真正理解数据结构，理解算法。

前人栽树，后人乘凉。本系列文章参考了以下文献，感谢前辈们的无私奉献！（排名不分先后）

以上资源可以关注下方微信公众号，回复关键字 资料 获取。

本文到此就结束了，如果您喜欢我的文章，可以关注我的微信公众号： 大大纸飞机

或者扫描下方二维码直接添加：

公众号

您也可以关注我的github：https://github.com/LtLei/articles

编程之路，道阻且长。唯，路漫漫其修远兮，吾将上下而求索。

上一篇下一篇

猜你喜欢

热点阅读