1

最近、時間計算量について読みましたが、クイックソートの平均時間計算量はO（nlog（n））であることがわかりました。

質問1：私が理解していないのは、時間計算量の方程式にlog（n）がどのように存在するかということです。

質問2：アルゴリズムの時間計算量を見つけるために常に大きなO表記を使用するのはなぜですか？他の表記を使わないのはなぜですか？

4

4 に答える 4

11

どのようlognにして複雑さの公式に取り掛かったのですか？

  • ステップごとに、前半と後半でアルゴリズムを再帰的に呼び出します。

  • したがって、必要なステップの総数は、問題を各ステップで2ずつ分割した場合 に、からnに到達するのにかかる回数です。したがって、実際には次のようなものを探しています。1
    k

    n / 2 /2 / 2 / ... /2 = 1
        ^
     (k times)

    ただし、方程式は実際には次のようになっていることに注意してくださいn / 2^k = 1。以来2^logn = n、取得しk = lognます。したがって、アルゴリズムに必要なステップ（反復）の数はO（logn）です。これにより、アルゴリズムが作成されます。O(nlogn)各反復はであるためですO(n)。

注：ここでの複雑さは正確ではありません。まれにクイックソートがに減衰しO(n^2)ます。これはピボットの選択によって異なります。「問題を各ステップで2つずつ分割する」は単純化したものですが、アルゴリズムの平均分析を変更するものではありません。

なぜ大きなO表記を使用するのですか？
シンプルでプラットフォームに依存しません。
opの正確な数（場合によっては比較も）は、プラットフォームによって異なります。（命令セットAが命令セットBよりも豊富な場合は、おそらくより多くの操作が必要になります）。 使用される方法はこれだけ
ではありません。実際のアプリケーションでは、正確な実行時間（秒単位）が非常に重要な要素であり、よく使用されます。

つまり、-大きなO表記法を使用すると、計算が簡単になります-アルゴリズムが漸近的に（無限大で）どのように動作するかについてのプラットフォームに依存しない近似。これにより、アルゴリズムの「ファミリ」を複雑さのサブセットに分割し、それらを簡単に比較できます。彼ら。

また、使用される他の表記法は、小さいo、シータ、および大きい/小さいオメガです。

于 2012-08-15T06:02:41.733 に答える
2

質問1.クイックソートの最悪の場合の時間計算量はO（n ^ 2）ですが、平均的な場合の複雑さはO（nlogn）です。logn係数は、ピボット、アルゴリズムがそれを選択する方法によって異なります。

クイックソートの最悪の場合の時間計算量は、ピボットがサイズ1要素とサイズ（n-1）要素の2つの領域を再帰的に生成する場合に発生しますが、平均的なケースは、生成される両方の領域のサイズがn/2になるようにピボットが2つの領域を選択する場合に発生します。 。

したがって、生成される漸化式はT（n）= 2T（n / 2）+Θ（n）です。

                  f(n)=Θ(n)     
                  h(n)=n^log2(2)=>n 
                  since f(n) = h(n) so
                  T(n)= f(n)logn =>n(logn).

（ここでは、クイックソートの最悪の場合の複雑さ（大きなO）はO（n ^ 2）であるため、Θ表記を使用しています。ここでは、平均的な場合の複雑さを計算しています。）

質問2.引数が無限大になる傾向がある場合でもアルゴリズムを制限する最悪の場合の時間計算量のアイデアを与えるため、大きなO表記を使用します。つまり、アルゴは少なくともこの時間計算量で実行され、それを超えることはできません。

小さいo、シータ、大きい/小さいオメガなどの他の表記法もありますが、これらは用途が限られているため、非常に頻繁に使用されます。

于 2012-08-15T10:01:39.470 に答える
1

コーメンらによるアルゴリズム入門をお読みください。第3章では、アルゴリズムの複雑さの分析についての適切な説明があります。使用されている漸近表記はBigOだけではないことがわかります。

于 2012-08-15T04:23:51.120 に答える
1

これは一般的なコンピュータサイエンスに関する質問ですが、質問へのコメントによってより完全に説明することができます-

質問1：log（n）は、問題がO（n）問題よりも係数log（n）の速度でスケーリングすることを示すためにあります。n * log（n）よりも小さい用語（nなど）は、最大の用語よりもスケーリングが遅いため、省略されています。

質問2：他のメトリックがあります。O（大きなO）は、問題の拡大の最悪の場合の割合です。コメント内の本のリンクを参照して、他の人が何であるか/意味するかを確認してください。

于 2012-08-15T04:25:53.203 に答える