[解決済み] どのようにすれば、ほとんどすべてのアルゴリズムを修正して、最良の場合の実行時間を持つようにできるか？

質問内容

からの質問です。 アルゴリズム入門 Cormenらによるものですが、これは宿題の問題ではありません。その代わり、自習になります。

いろいろ考えたり、Googleで検索したりしました。思いつく答えは

• 別のアルゴリズムを使用する。
• ベストケースを入力させる
• アルゴリズムを実行するために、より良いコンピュータを使用する

しかし、これらは正しいとは思えません。アルゴリズムを変えることと、アルゴリズムの性能を上げることは同じではありません。また、より良いコンピュータを使えばスピードが上がるかもしれませんが、アルゴリズムが良くなるわけではありません。これは本の冒頭の質問なので、私が見落としている単純なことだと思います。

では、どのようにすれば、ほとんどすべてのアルゴリズムを修正して、ベストケースの実行時間を確保することができるのでしょうか。

どのように解決するのか？

どのようなアルゴリズムでも、最良の場合の時間複雑度が O(n) 入力がこの特別なケースに一致する場合、キャッシュされたハードコードされた答え（または他の簡単に得られる答え）を返すという特別なケースを追加することによって。

例えば、任意のソートに対して、最良のケースを作ることができます。 O(n) は、配列がすでにソートされているかどうかをチェックし、ソートされている場合はそのまま返します。

平均値や最悪のケースには影響しないことに注意してください。 O(n) また、基本的にアルゴリズムの最良の場合の時間複雑性を向上させます。

注：入力の大きさが有限である場合、同じ最適化により、最良のケースである O(1) というのは、この場合の入力の読み取りは O(1) .