概念

即使计算机无限快，存储器也是免费的，依然需要研究算法，你会希望采用最容易实现的算法。

算法就像计算机硬件一样，是一种技术。总体的系统性能不仅依赖于选择快速的硬件，还依赖于选择有效的算法。

在算法领域，lg表示以2为底取对数，而非以10为底。

习题

1.2-1 给出一个实际应用的例子，它在应用这一层次上要求有算法性的内容。讨论其中所涉及算法的功能。

比如一个应用程序，用于将输入的图片如果有倾斜的话进行矫正。其中涉及了图像处理算法如边缘检测。

1.2-2 假设我们要比较在同一台计算机上插入排序和合并排序的实现。对于规模为n的输入，插入排序要运行8n²步，而合并排序要运行64nlgn步。当n取怎样的值时，插入排序的性能要优于合并排序？

令8n²<64nlgn, 有n<8lgn

==> n/8<lgn

==> 2^(n/8)<n

==> 2^(n/4)<n² ,

采用探测法，得到n≤43，所以在2≤n≤43时，插入排序的性能优于合并排序

1.2-3 对于一个运行时间为100n²的算法，要使其在同一台机器上，比一个运行时间为2ⁿ的算法运行得更快，n的最小取值是多少？

令100n²<2ⁿ，得 lg100+2lgn<n

==>近似于6.8+2lgn<n

通过探测法得n≥15，n最小取值为15

思考题

1-1 算法运行时间比较

　　对于下表中每一个函数f(n)和时间t， 求出可以在时间t内被求解出来的问题的最大规模n。假设解决该问题的算法解决该问题需要f(n)微秒。

列方程f(n)=t（t的单位：微秒），求解出n即可。

《算法导论》（第二版）【1.2】笔记及习题解答

原文：https://www.cnblogs.com/wing-Zuo/p/12387696.html