『算法导论』第 1 章:算法在计算中的作用

主要内容

本章介绍了算法的定义、作用和重要性。

简单地说,算法(algorithm)是定义良好的计算过程。算法是一系列的计算步骤,用来将输入数据转换成输出结果。算法能够解决各种类型的问题,应用面很广。计算机的计算资源和存储资源是有限的,时间和空间上有效的算法能够有效地利用这些有限的资源。解决同一问题的不同算法,效率常常相差很大,这种效率上差距的影响往往比硬件和软件的差距还要大。拥有扎实的算法知识和技术基础对程序员来说非常重要。

习题解答

本章习题完成于2018年3月6日。

练习题

1.1-1 解答:奥运会的奖牌榜根据金银铜牌的个数排序。

1.1-2 解答:除了速度之外,耗费存储资源的大小也是效率的量度。

1.1-3 解答:链表的优势在于,可以按需分配存储资源,可以在任意位置插入和删除节点;局限在于,每个节点需要额外的空间存储指针变量,无法用下标快速访问节点。

1.1-4 解答:相似之处在于,它们都要寻找最短路径;不同之处在于,最短路径问题有最优算法,旅行商问题只有近似算法。

1.1-5 解答:导航软件给出的最短路径,只有最佳解才行;排版软件断行算法,近似最佳也可以。

1.2-1 解答:比如排版软件,当出现一长串英文单词时,需要算法计算在哪个位置断行最美观。

1.2-2 解答:当$n \le 42$时,$8n^2<64n\log_{2}n$成立。

1.2-3 解答:当$n \ge 15$时,$100n^2<2^n$成立。

思考题

1.1 解答:即求取$f(n) = t$的解。计算结果略。