アルゴリズムの最適な時間複雑度を見つけるにはどうすればよいですか？

Question

いくつかのアルゴリズムで問題を解決した後、時間の複雑さを改善しようとするまで、つまり、あなたの現在の時間の複雑さが可能な限り最高であり、漸近的な時間の複雑さにはそれ以上の改善はないと知っていますか？ インタビュアーが最適化できないアルゴリズムをさらに最適化するように求めている場合は、インタビューの際にクリアしたいと思っていました。私が開発したアルゴリズムがすでに最高のものであり、 "最適化を行うことができますか？

Answer 1

アルゴリズムの時間複雑度の下限を証明する方法を尋ねています。指数関数的な数を生成しようとしているときや指数関数的な時間よりもうまくいっていない場合や、ソートされていないリストで最大の数を見つけなければならない場合は、その数は最良の時間範囲が線形であるようにします。しかし、これは非常に難しい場合もあります。コンピュータサイエンスにおける最も重要なオープンな問題の1つは、誰かがNP完全な問題のいずれかの下限を証明できれば解決できるP = NPの推測です。このアプローチには膨大な時間と労力がかかりましたが、大きな成果は出ていません。さらに、可能な限り低いbig-Oは、必ずしもより良い定数を持つより高速のアルゴリズムがないことを意味するわけではありません。

実際には、一定の要因が問題になるため、実装で一定の要因を改善できるかどうかを尋ねることがあります。また、インタビュー中に物事を証明しようとすると、最高のヒットまたはミスです。アルゴリズムをさらに最適化するように求められた場合は、通常、問題を迅速に解決する方法があり、インタビュアーは通常、質問をして、そのような解決策に向けてあなたを促すヒントを与えるためです。

特定の証明手法に関して、比較ソートにバインドされたnlog（n）の証明は、見るべき面白いものです。証明の本質的な考え方は、n！リストの可能な順列と最悪の場合、各比較はそれらの半分しか除去できない。スターリングの近似によって、これはnlog（n）の境界に変わります。それは言われている、これはここで直接議論するには広すぎる複雑なトピックです。