算法导论：练习1.1
source link: https://sexywp.com/clrs-1-1.htm
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
今天跟一个朋友约定，一起开始认真学习算法。于是翻出了买了多年，但是从未看过的《算法导论》。认认真真看起来。记得多年前，就一直在这本书上受挫，这是除了《代码大全》外，另一本归入“买了永远不会看”分类的书。我现在的想法是，我看完这本书，并认真完成所有的练习，是否肯定可以获得一定程度上的收获呢？哪怕是花去人生中的很多年，也一定要完成。
1. 给出一个真实世界的例子，其中包含着下列的某种计算问题：排序，确定多矩阵相乘的最佳顺序，或者找出凸壳。
这是1.1节的第一个练习题，如果认真看题目，并思考的话，会发觉，这其实是一个相当困难的题目。反正我的第一个直觉就是，我不可能想出来真实世界中有什么地方是要用到多矩阵相乘，或者找出凸壳这种东西的。对于矩阵的认识，我停留在大学时代学过的线性代数的残留记忆的水平，约等于是一无所知。当年也是如此，学习线性代数，也只是当成一门数学来学习，从来没有想到过，这门学科可以用在真实生活中的什么地方。而美国随便一本计算机教材的第一章，第一节，要求学生思考真实生活中什么地方用到这个数学的知识，正是以把知识和生活紧密结合为导向，向学生传递知识，如果学生真的认真思考，很难想见这些学生会没有成就，学生对此问题的理解会不深。
而反思自己，无论是学习线性代数的时候，还是学习算法的时候，我从来没有想到过，某个数学概念和或者某个算法跟真实生活的联系，也难怪，学过了就忘记，要是记住了，那才真的是奇怪。
要说真实世界用到排序的例子，那是相当简单的，我决定每个人至少能说出个十种八种。我就说一个我最近生活中常常碰到的，就是在12306购买火车票的时候，我最常用的，就是按照发车时间顺序排序，或者在使用手机查询列车时刻表的时候，按照列车行程时间排序，以便我买到车程最短的列车。
2. 除了运行速度以外，在真实世界问题背景中，还可以用那些效率指标？
关于算法效率指标，我马上就能想到的还有一个，就是算法耗费的内存。我们常说时间换空间，或者空间换时间，就是说这二者是一对矛盾，所以，衡量算法效率，除了时间，就是空间。也就是存储。
3. 选择你原来见过的某种数据结构，讨论一下其长处和局限性。
先选一个最简单的，就是数组。这是一种线性的数据结构。其长处是按照下标读取元素的速度相当快而且简单。缺点是，一旦需要数组元素变动，操作就会极为复杂，比如在中间插入一个元素，后面所有的原素都要跟着挪动位置。另外一个缺点就是数组的原素个数是固定的。数组的空间是静态的。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK