5

シータ表記のわかりやすい英語の説明は何ですか？可能な限り正式な定義を少なくし、単純な数学を使用します。

シータ表記はビッグO表記とどのように異なりますか？誰かが平易な英語で説明できますか？

アルゴリズム分析では、どのように使用されますか？私は混乱しています？

4

2 に答える 2

6

アルゴリズムの実行時間がBigTheta（f（n））の場合、f（n）によって上下に漸近的に制限されます。Big Oは、境界が上にあることを除いて同じです。

直感的に、Big O（f（n））は、「一定の要因と項を無視すると、実行時間がf（n）を超えることはないと確信できます」と述べています。大まかに言うと、実行時間を「悪い」と考えると、BigOは最悪のケースです。Big Theta（f（n））は、「一定の要因と項を無視すると、実行時間は常にf（n）として変化することを確信できます」と述べています。言い換えると、Big Thetaは既知のタイトバウンドです。これは、最悪の場合と最良の場合の両方です。

直感の最後の試み：BigOは「一方的」です。O（n）の実行時間もO（n ^ 2）およびO（2 ^ n）です。これはビッグシータには当てはまりません。O（n）のアルゴリズム実行時間がある場合は、それがBig Theta（n ^ 2）ではないという証拠がすでにあります。Big Theta（n）である場合とそうでない場合があります

例は比較ソートです。情報理論によると、ソートには少なくともceiling（n log n）の比較が必要であり、実際にはO（n log n）アルゴリズム（nは比較の数）を発明したため、ソートの比較はBig Theta（n log n）です。

于 2012-09-08T17:34:16.643 に答える
2

私はいつもこれを簡単な言葉で言いたかったのです。これが私の試みです。

アルゴリズムの時間または空間の複雑さがで表される場合

  • Big O：Ex O（n）-nが上限であることを意味します。最終値はn以下である可能性があります。

  • ビッグオメガ：ExΩ（n）-nが下限であることを意味します。最終値はn以上になる可能性があります。

  • シータ：ExΘ（n）-nが唯一の可能な値であることを意味します。（上限と下限の両方）

于 2013-06-20T00:31:30.340 に答える