这是 Cormen 等人的Introduction to Algorithms中的一个问题，但这不是家庭作业问题。相反，它是自学。
我想了很多，在谷歌上搜索。我能想到的答案是：
- 使用另一种算法。
- 给它最好的情况输入
- 使用更好的计算机来运行算法
但我不认为这些是正确的。更改算法与使算法具有更好的性能不同。同样使用更好的计算机可能会提高速度，但算法并不好。这是本书开头的一个问题，所以我认为这是我忽略的简单问题。
那么我们如何修改几乎所有算法以获得良好的最佳情况运行时间呢？
问问题
14693 次
7 回答
50
您可以修改任何算法以O(n)通过添加特殊情况来获得最佳情况时间复杂度，如果输入与此特殊情况匹配 - 返回缓存的硬编码答案（或其他一些容易获得的答案）。
例如，对于任何排序，您可以O(n)通过检查数组是否已经排序来做出最佳情况 - 如果是，则按原样返回。
请注意，它不会影响平均或最坏情况（假设它们不是更好O(n)），并且您基本上可以提高算法的最佳情况时间复杂度。
注意：如果输入的大小是有界的，同样的优化会产生最好的情况O(1)，因为在这种情况下读取输入是O(1)。
于 2013-08-07T12:50:29.060 回答
5
如果我们可以在系统本身的计算模型中为该算法引入一条指令，我们就可以在一条指令中解决问题。
但是您可能已经发现，这是一种非常不切实际的方法。因此，修改任何算法以获得最佳情况运行时间的通用方法几乎是不可能的。我们最多可以做的是在算法中对各种问题中发现的一般冗余进行调整。
或者，您可以通过采用最佳案例输入来天真。但同样，这实际上并没有修改算法。事实上，在计算系统本身中引入算法，不是非常不切实际，也不是算法的修改。
于 2015-07-23T07:20:28.507 回答
1
我们可以修改算法以获得最佳案例运行时间的方法是：
- 如果算法处于其目的/解决方案的点，例如，对于递增排序，它已经是升序排序等等。
- 如果我们修改算法以便我们输出和退出仅用于其目的，从而迫使多个嵌套循环只是一个
于 2017-06-16T14:53:02.150 回答
1
我们有时可以使用随机算法来进行随机选择，以进行概率分析，从而提高运行时间。
于 2018-09-02T22:13:42.850 回答
0
我认为解决这个问题的唯一方法是算法的输入。因为时间复杂度分析中的案例只取决于我们的输入，它有多复杂，它倾向于运行算法多少次。在这个分析中，我们决定我们的情况是最好的、平均的还是最差的。因此，我们的输入将决定每种情况下算法的运行时间。或者我们可以改变我们的算法以改进所有情况（降低时间复杂度）。
这些是我们可以实现良好的最佳情况运行时间的方法。
于 2019-07-03T07:39:40.870 回答
0
我们可以针对某些特殊情况修改算法，因此如果输入满足该条件，我们可以输出预先计算的答案。通常，最佳案例运行时间并不是算法的好衡量标准。我们需要知道算法在最坏情况下的表现。
于 2021-03-26T06:53:03.733 回答
0
我只是在寻找答案时进行了这个讨论。我认为只有一种方法可以通过固定输入而不是可变输入来使任何算法成为最佳情况。如果我们总是有一个固定的输入，那么成本和时间复杂度总是 O(1)
于 2021-04-03T16:01:06.360 回答