[解決済み] 定数時間や対数時間よりも、nやnlog(n)の方が良いのでしょうか？

質問内容

CourseraのPrincetonのチュートリアルで、講師がよく遭遇するorder-of-growth関数について説明しています。彼は、線形および線形ithmicの実行時間は我々が目指すものであり、その理由は入力サイズが大きくなると実行時間も大きくなるからだと言っています。私は以前、彼が効率的なアルゴリズムにとって線形成長順序は不満足であると言っているのを聞いたことがあるので、ここが彼の間違いであると思います。

また、講演中に、実行時間の違いをプロットしたグラフを見せましたが、実行時間が一定で対数の方が効率が良さそうでした。これは間違いなのか、それとも真実なのか？

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

あなたは、これらの発言がなされたはずの、より広い文脈を見逃しているのです。問題の種類によって要求されるものが異なり、また、多くの場合、どの程度の作業が必要かという理論的な下限値さえも存在します。 絶対に必要 どんな手段であれ、それを解決するために。

単純なコレクションのすべての要素をソートしたりスキャンしたりするような操作では、出力が入力のすべての要素に依存するので、それらの操作のためのコレクションの要素数のハードな下界を作ることができます。[1] したがって、O(n)またはO(n*log(n))が最良となる。

他の種類の操作、例えばハッシュテーブルやリンクリストの1つの要素にアクセスしたり、ソートされた集合の中を探したりする場合、アルゴリズムは入力をすべて調べる必要はありません。このような場合、O(n)演算は恐ろしく遅くなる。

[1] また、情報理論的な議論から、比較によるソートも n*log(n) の下界を持つことに注目する人もいるでしょう。ある種の入力に対して、比較によらないソートアルゴリズムがあり、これを打ち負かすことができます。