CLRS1 算法在计算中的应用

2017-05-04 | 阅读：次

介绍

在CLRS系列的文章里，我会记录学习算导这本书的收获，并整理习题~

练习1.1-1 给出现实生活中需要排序的一个例子或者现实生活中需要计算凸壳的一个例子。

排序：听歌时将歌曲按字典排序，方便查找。
凸壳：平面上有n点，其中没有三个点是共线的，求包含这些点的面积最小的n边形

练习1.1-2 除速度外，在真实环境中还可能使用哪些其它有关效率的量度？
```
资源占用
```
练习1.1-3 选择一种你以前已知的数据结构，并讨论其优势和局限.
```
链表。可随意调整大小，但不支持随机访问。
```
练习1.1-4 How are the shortest-path and traveling-salesman problems given above similar? How are they different?
```
最短路径找两点之间的最短路径，而旅行商问题要经过许多给定点，并回到起点。
```
练习1.1-5 Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is “approximately” the best is good enough.
```
1. 一元一次方程的精确解。
2. 一元一次方程的近似解。
```

练习1.2-1 Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved.
```
小娜语音识别，需要用到神经网络算法
通过语音识别算法来将语音转化为文字
```
练习1.2-2 Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in steps, while merge sort runs in steps. For which values of n does insertion sort beat merge sort?
```
令8n^2 = 64nlgn, 得到当2 < n < 43时，insertion较优。
```
练习1.2-3 What is the smallest value of n such that an algorithm whose running time is runs faster than an algorithm whose running time is on the same machine?
```
n = 15
```

这个……知道差距非常非常大就好了吧