这是Cormen的算法导论中的一个问题.但这不是一个家庭作业问题而是自学.
我已经想了很多,并在谷歌搜索.我能想到的答案是: -
但我不认为这些是正确的.更改算法与使算法具有更好的性能不同.使用更好的计算机也可以提高速度,但算法并不是更好.这是本书开头的一个问题,所以我觉得这很简单,我忽略了.
那么我们如何修改几乎所有算法以获得良好的最佳运行时间？
ami*_*mit 42
您可以O(n)通过添加特殊情况修改任何算法以获得最佳案例时间复杂度,如果输入符合此特殊情况,则返回缓存的硬编码答案(或其他一些容易获得的答案).
例如,对于任何排序,您可以O(n)通过检查数组是否已经排序来做出最佳情况- 如果已排序,则按原样返回.
请注意,它不会影响平均或最差情况(假设它们并不是更好O(n)),并且您基本上可以提高算法的最佳案例时间复杂度.
注意:如果输入的大小是有界的,那么相同的优化是最好的情况O(1),因为在这种情况下读取输入是O(1).
如果我们可以在系统本身的计算模型中引入该算法的指令,我们就可以在一条指令中解决问题.
但正如您可能已经发现这是一种非常不现实的方法.因此,修改任何算法以获得最佳案例运行时间的通用方法几乎是不可能的.我们在max处可以做的是在算法中应用针对各种问题中发现的一般冗余的调整.
或者你可以通过最好的案例输入来天真.但同样,这实际上并没有修改算法.实际上,将算法引入计算系统本身,而不是非常不现实,也不是算法中的修改.