栖木之境

数据结构

《算法 + 数据结构 = 程序》 是 Pascal 语言之父 Niklaus Emil Wirth 写过的一本非常著名的书。而作为书名的这句话也成为了计算机科学的经典名句。可见,对于程序设计来说,算法和数据结构的关系密不可分。

在学习之前,首先我们要弄清楚什么是算法?什么是数据结构?为什么要学习算法和数据结构?

简单来说,「算法」就是解决问题的方法或者过程。如果我们把问题看成是函数,那么算法就是将输入转换为输出的过程。「数据结构」是数据的计算机表示和相应的一组操作。「程序」则是算法和数据结构的具体实现。

如果我们把「程序设计」比作是做菜的话,那么「数据结构」就是食材和调料,「算法」则是不同的烹饪方式,或者可以看作是菜谱。不同的食材和调料,不同的烹饪方式,有着不同的排列组合。同样的东西,由不同的人做出来,味道自然也是千差万别。

至于为什么要学习算法和数据结构?

还是拿做菜举例子。我们做菜,讲究的是「色香味俱全」。程序设计也是如此,对于待解决的问题,我们追求的是:选择更加合适的「数据结构」,使用花费时间更少、占用空间更小的「算法」。

我们学习算法和数据结构,是为了学会在编程中从时间复杂度、空间复杂度方面考虑解决方案,训练自己的逻辑思维,从而写出高质量的代码,以此提升自己的编程技能,获取更高的工作回报。

当然,这就像是做菜,掌握了食材和调料,学会了烹饪方式,并不意味着你就会做出一盘很好吃的炒菜。同样,掌握了算法和数据结构并不意味着你就会写程序。这需要不断的琢磨和思考,并持续学习,才能成为一名优秀的厨师(程序员)。

算法复杂度

算法复杂度(Algorithm complexity):在问题的输入规模为 n 的条件下,程序的时间使用情况和空间使用情况。

「算法分析」的目的在于改进算法。正如上文中所提到的那样:算法所追求的就是所需运行时间更少(时间复杂度更低)、占用内存空间更小(空间复杂度更低)。所以进行「算法分析」,就是从运行时间情况、空间使用情况两方面对算法进行分析。

比较两个算法的优劣通常有两种方法:

大多数情况下,我们会选择第 2 种方式。因为第 1 种方式的工作量实在太大,得不偿失。另外,即便是同一个算法,用不同的语言实现,在不同的计算机上运行,所需要的运行时间都不尽相同。所以我们一般采用预先估算的方法来衡量算法的好坏。

采用预先估算的方式下,编译语言、计算机运行速度都不是我们所考虑的对象。我们只关心随着问题规模 n 扩大时,时间开销、空间开销的增长情况。

这里的「问题规模 n」指的是:算法问题输入的数据量大小。对于不同的算法,定义也不相同。

排序算法中:n 表示需要排序的元素数量。

查找算法中:n 表示查找范围内的元素总数:比如数组大小、二维矩阵大小、字符串长度、二叉树节点数、图的节点数、图的边界点等。

二进制计算相关算法中:n 表示二进制的展开宽度。

一般来说,问题的输入规模越接近,相应的计算成本也越接近。而随着问题输入规模的扩大,计算成本也呈上升趋势。