1. ホーム
  2. 質問と答え
  3. 同じタスクのΘ（n）時間アルゴリズムに対してΘ（n log n）時間アルゴリズムを使用することを選択する理由

同じタスクのΘ（n）時間アルゴリズムに対してΘ（n log n）時間アルゴリズムを使用することを選択する理由

2016-07-06 10 views

答えて

2

Big OとBig Thetaの表記は、任意に大きな入力サイズの場合、パフォーマンスがいくらか限界に向かう傾向があることを暗示しています。たとえば、関数99999999nはO（n）ですが、関数（1/9999999999）n^2はO（n^2）です。しかし、妥当なサイズの入力（無限大ではない）に対して、O（n^2）関数は明らかに高速である可能性が高い。

つまり、入力データについて仮定することができれば、一般的に悪化したアルゴリズムがより良い結果を示す場合があります。

上記の概念の実際の例はソートです - 配列が既にソートされている場合（バブルソート）にO（n）時間で実行するアルゴリズムがあります。すでに多くの配列がソートされていることがわかっている場合は、この理由でバブルソートとマージソートを使用することを選択できます。

さらに時間効率の良いアルゴリズムを使用したくない別のコーナーケースは、スペース効率です。たぶん、ごくわずかなRAMで組み込みデバイスでプログラミングしているかもしれません。できるだけ完全に時間効率的であるよりもむしろメモリと廃棄物を少し使います。

出典

2016-07-06 18:24:36 nhouser9

+0

この詳細な対応をありがとうございます。たくさんの意味があります。また、あなたがフォローアップに答える気にならないなら、私の教授。ビッグシータは「ベストケースの最悪ケースタイム」と表現することができます。これを別の言葉で説明できますか？私の理解は、大きなシータが最悪の場合の入力サイズの下限であるということです。しかし、私は聞いたことをちょうどparattingと私はそれが意味するものを確認していません。 – mdm508

+0

@ mdm508 Big Oは最悪の場合の時間の複雑さであり、大きなOmegaは最良の場合の時間の複雑さです。ビッグシータは両方の組み合わせです - 何かがθ（n^2）ならば、最悪の場合と最良の場合の両方で、関数k（n^2）によって上下に制限されることを意味します。ここでnは任意に大きいkは任意の定数である。あなたの教授がそれを「最悪の場合の最良のケース」と呼んだのは、私が推測していることです。これがアップヴォートを助け、受け入れられた答えが大いに評価されるならば。 – nhouser9

+0

@ mdm508心配しないでください - 私の説明がどんな場合でも助けてくれることを願っています。 – nhouser9

関連する問題

 関連する問題