Question

算法导论答题笔记_0x1

Answer 1

1.1-5
原题：
提供一个现实生活的问题，其中只有最佳解才行。然后提供一个问题，其中近似最佳的一个解也足够好。
回答：
最佳解唯一问题最简单的就是找第一名，必须要满足条件最优者才行。
近似解的问题比如机器学习或者神经网络，许多时候只需找到近似最优解或者局部最优解就行。
而且机器学习和神经网络比较特殊，许多时候那些看起来是局部最优（这里指误差函数结果小的解）的解往往效果十分好。

1.2-1 （开放问题）
原题：
给出在应用层需要算法内容的应用的一个例子，并讨论设计的算法的功能。
回答：
这里我对应用层的意思不是很理解。可能是指网络中的应用层？然后手机会有手势识别，这就需要算法去匹配你的手势。可能会采用某种分类器，就是分类东西的算法，比如各种机器学习算法。

1.2-2
原题：
假设我们正比较插人排序与归并排序在相同机器上的实现，对规模为n的输人，插人排序运行8n ² 步，而归并排序运行64nlog ₂ n步。问对哪些n值，插人排序优于归并排序？
回答：
1<=n<=43时。8x43 ² =14792 < 64x43log ₂ 43=14933；8x44 ² =15488 > 64x44log ₂ 44=15374。