为什么要研究算法?
计算机也许是快的,但他们不是无限快的。存储器也许是廉价的,但不是免费的。
所以计算时间是一种有限资源,存储器中的空间也一样。
高效的算法将帮助你更有效的利用这些资源。
效率
为求解相同的问题而设计的不同算法在效率方面常常具有显著的差别。这些差别可能比由于硬件和软件照成的差别要重要的多。
例如使用插入排序和归并排序同时排序1e7次方个数。
算法与其他技术
算法与其他技术也关系密切,往往在较大规模问题的时候,不同算法之间的效率差别将会更为显著。
我们应该像计算机硬件一样把算法看成一种技术。
练习
1.2.1给出在应用层需要算法内容的应用的一个例子,并讨论涉及的算法的功能。
为了使用Cache解决了cpu与主存间的速度不匹配,我们需要把内存块映射到Cache,为了提高内存块的命中率,而出现了多种替换策略,使用高效的策略,可以提高Cpu对Cache的命中率。
1.2.2假设我们正比较插入排序和归并排序在相同机器上的实现。对规模为n的输入,插入排序运行8n^2步,而归并排序运行64nlgn步。问对那行n值,插入排序优于归并排序?
当n<8*lgn时
1.2.3n的最小值为何值时,运行时间为100n^2的一个算法在相同机器上快于运行时间为2^n的另一个算法?
当n=14时
可以通过代码简单验证
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int n=20;
while(100*n*n<pow(2,n))
{
n=n-1;
}
cout<<100*n*n<<endl;
cout<<pow(2,n)<<endl;
cout<<n<<endl;
return 0;
}
思考题1.1
本思考题图片答案转自https://www.cnblogs.com/onepixel/articles/7674659.html