数据结构
《算法 + 数据结构 = 程序》 是 Pascal 语言之父 Niklaus Emil Wirth 写过的一本非常著名的书。而作为书名的这句话也成为了计算机科学的经典名句。可见,对于程序设计来说,算法和数据结构的关系密不可分。
在学习之前,首先我们要弄清楚什么是算法?什么是数据结构?为什么要学习算法和数据结构?
简单来说,「算法」就是解决问题的方法或者过程。如果我们把问题看成是函数,那么算法就是将输入转换为输出的过程。「数据结构」是数据的计算机表示和相应的一组操作。「程序」则是算法和数据结构的具体实现。
如果我们把「程序设计」比作是做菜的话,那么「数据结构」就是食材和调料,「算法」则是不同的烹饪方式,或者可以看作是菜谱。不同的食材和调料,不同的烹饪方式,有着不同的排列组合。同样的东西,由不同的人做出来,味道自然也是千差万别。
至于为什么要学习算法和数据结构?
还是拿做菜举例子。我们做菜,讲究的是「色香味俱全」。程序设计也是如此,对于待解决的问题,我们追求的是:选择更加合适的「数据结构」,使用花费时间更少、占用空间更小的「算法」。
我们学习算法和数据结构,是为了学会在编程中从时间复杂度、空间复杂度方面考虑解决方案,训练自己的逻辑思维,从而写出高质量的代码,以此提升自己的编程技能,获取更高的工作回报。
当然,这就像是做菜,掌握了食材和调料,学会了烹饪方式,并不意味着你就会做出一盘很好吃的炒菜。同样,掌握了算法和数据结构并不意味着你就会写程序。这需要不断的琢磨和思考,并持续学习,才能成为一名优秀的厨师(程序员)。
算法复杂度
算法复杂度(Algorithm complexity):在问题的输入规模为 n 的条件下,程序的时间使用情况和空间使用情况。
「算法分析」的目的在于改进算法。正如上文中所提到的那样:算法所追求的就是所需运行时间更少(时间复杂度更低)、占用内存空间更小(空间复杂度更低)。所以进行「算法分析」,就是从运行时间情况、空间使用情况两方面对算法进行分析。
比较两个算法的优劣通常有两种方法:
- 事后统计:将两个算法各编写一个可执行程序,交给计算机执行,记录下各自的运行时间和占用存储空间的实际大小,从中挑选出最好的算法。
- 预先估算:在算法设计出来之后,根据算法中包含的步骤,估算出算法的运行时间和占用空间。比较两个算法的估算值,从中挑选出最好的算法。
大多数情况下,我们会选择第 2 种方式。因为第 1
种方式的工作量实在太大,得不偿失。另外,即便是同一个算法,用不同的语言实现,在不同的计算机上运行,所需要的运行时间都不尽相同。所以我们一般采用预先估算的方法来衡量算法的好坏。
采用预先估算的方式下,编译语言、计算机运行速度都不是我们所考虑的对象。我们只关心随着问题规模 n 扩大时,时间开销、空间开销的增长情况。
这里的「问题规模 n」指的是:算法问题输入的数据量大小。对于不同的算法,定义也不相同。
排序算法中:n 表示需要排序的元素数量。
查找算法中:n 表示查找范围内的元素总数:比如数组大小、二维矩阵大小、字符串长度、二叉树节点数、图的节点数、图的边界点等。
二进制计算相关算法中:n 表示二进制的展开宽度。
一般来说,问题的输入规模越接近,相应的计算成本也越接近。而随着问题输入规模的扩大,计算成本也呈上升趋势。