第一章 算法在计算中的角色

• 什么是算法？
• 为什么算法值得研究？
• 跟在计算机中使用的其他技术相比，算法处在什么地位？

1.1节 算法

第一种定义
算法是任意一个定义清晰的计算过程，该计算过程取一个值或者一组值作为输入，计算出一个值或者一组值作为输出。
根据该非正式的算法定义可以导出哪些结论？
一个算法就是将输入转换成输出的一系列的计算步骤。

第二种定义
一个算法就是解决描述清楚的可计算问题的一种工具。
对问题的描述就是描述了输入和输出之间的关系，算法实际上是描述了实现这种输入和输出关系的计算过程。

排序问题
定义
输入：一系列的数。

输出：，其中满足。

1.2节 算法是一种技术

算法是一种帮助你有效率地使用计算时间和空间等资源的技术。

因为计算机的运行速度虽然很快，但不是无穷快；计算机的内存虽不贵，但也不是免费的，所以计算所用时间和计算所需空间是一种有限的资源。

因为计算所需时间和计算所需空间是一种有限的资源，所以需要有效地使用。

算法的效率问题

假设有两台计算机，分别是计算机A和计算机B，其中计算机A可在1秒钟执行1百亿(量级为)条指令，计算机B可在1秒钟内执行1千万(量级为)条指令。

假设运行在计算机A上的插入排序算法代码实现满足：

• 如果要对个数排序，则有条指令；

运行在计算机B上的归并排序算法的代码实现满足：

• 如果要对个数排序，则有条指令；

问题1 现有1千万(量级为)个数，占据的内存大约为76.3MB，让较快的计算机A运行插入排序，让较慢的计算机B运行归并排序。
则排序算法在计算机A上花费时间为

排序算法在计算机B上花费的时间为

问题2 现有1亿(量级为)个数，占据分内存大约是763MB，让较快的计算机A运行插入排序，让较慢的计算机B运行归并排序。
则排序算法在计算机A上花费时间为

排序算法在计算机B上花费的时间为

规律：

• 随着问题的规模的增大，归并排序的优势也会越来越大；
• 使用一个运行时间增长较慢的算法，即使用了较差的编译器，算法在不同计算机上的运行时间可相差17倍；

算法跟计算机里其他技术的关系

几个简单的观察：

• 系统的性能不仅取决于快速的硬件，而且取决于选择高效的算法。
• 随着计算机能力的不断提升，使用计算机来解决的问题的规模也比之前的大了。
• 更大规模的问题使得区分算法的效率变得尤为重要。

算法处在现代计算机技术的核心位置。

• 硬件设计会使用算法
• 图形用户界面GUI设计依赖算法
• 网络寻路极其依赖算法
• 编译器、解释器、汇编器大量使用算法