1

アルゴリズムの最悪の場合の時間の複雑さとその上限との関係/違いは何ですか?

4

2 に答える 2

3

「上限」という用語は、次の 2 つの可能性を指す可能性があるため、あまり明確ではありません。

  1. アルゴリズムの上限 - アルゴリズムが決してそれよりも「遅く」実行できない境界。これは基本的に最悪の場合のパフォーマンスなので、これが意味するものであれば、答えは非常に簡単です。

  2. big-O 記法。特定の分析の下でのアルゴリズムの複雑さの上限を示します。big-O 表記は関数のセットであり、最悪の場合、平均的な場合、さらには最良の場合を含む、アルゴリズムのあらゆる分析に適用できます。

クイックソートを例に取りましょう。

クイック ソートにはO(n^2)、最悪の場合のパフォーマンスとO(nlogn)平均的な場合のパフォーマンスがあると言われています。1 つのアルゴリズムに 2 つの複雑さがあるのはなぜですか? 単純な、平均的なケースの分析を表す関数と、最悪のケースを表す関数は、まったく異なる関数であり、それぞれに大きな O 表記を適用できます。制限はありません。

さらに、ベストケースに適用することもできます。配列が既にソートされているかどうかを最初にチェックし、ソートされている場合はすぐに停止するクイックソートの小さな最適化を検討してください。これは実質的なO(n)操作であり、この動作を提供する入力がいくつかあるため、アルゴリズムの最良のケースの複雑さは次のようになると言えます。O(n)

于 2015-04-28T08:43:35.863 に答える
0

最悪のケースと大きな O(UPPER BOUND) の違いは 、最悪のケースはコードに実際に発生するケースであり 、上限は過大評価であり、大きな O を計算するために設定した仮定であり、そうではないということです。起こらなければならない

挿入ソートの例:

最悪の場合：

数字はすべて逆に配置されているため、すべての数字を配置して移動する必要があります

擬似コード

for j=2 to n
  do key = a[i]
  i=j-1
  while i>0 & a[i]>key
    do a[i+1] = a[i]
    i=i-1
  end while
  a[i+1]=key
end for

上界：

内部ループの順序は毎回 i =n-1 であると仮定しますが、実際には毎回変更可能であり、毎回 n-1 になることはできませんが、大きな値を計算するためにそれを想定/過大評価しました〇

于 2018-09-25T15:22:06.133 に答える