なぜQuickSortがn log nなのかを直感的に説明できますか？

誰かがQuickSort n log nを作るのに直感的かつ正式な、「プレーン・イングリッシュ」の説明を与えることができますか？私の理解から、n個のアイテムを渡す必要があります。そして、このログをn回実行します...このログをn回実行する理由を単語に入れる方法がわかりません。なぜQuickSortがn log nなのかを直感的に説明できますか？

出典

2012-05-03 Jim_CS

各分割操作では、O（n）回の操作（配列に対して1回のパス）が必要です。平均では、各パーティショニングは配列を2つの部分に分割します（これはlog n操作までを合計します）。全体では、O（n * log n）回の操作があります。

I.e.平均log n分割操作では、各分割にはO（n）回の操作が必要です。

出典

2012-05-03 05:24:00

log nの部分は、（少なくとも理想的には）反復ごとに入力を半分に分割するという事実に由来します。 N個のアイテムから始め、毎回半分に分割すると、ログ（N）回の反復後に1アイテムまで減少することを意味します。たとえば、128個のアイテムから始めて、64,32,16,8,4,2,1アイテム~7回の繰り返しのグループに分割します（ログ（128）= 7）。

O（n log n）の全体的な複雑さに対してそれぞれO（n）の複雑さを持つO（log N）演算で終わるように、それらの反復のそれぞれが配列全体をスキャンします。

Big-OはO（N ）です。これは、パーティション要素の十分に悪い選択が、アレイを片側の1つの要素に、アレイの残りの部分全体を別の要素に分割する可能性があるという事実から生じる。これが繰り返されるたびに発生すると、N個の反復が1つの要素に分割されるので、全体的にO（N * N）の複雑さを持つN回の操作が得られます。

実際の実装では、通常はその前に停止しますが、それはあなたが行ける最も遠いものです。

出典

2012-05-03 05:24:55

+10

ありがとうございます。ここで受け入れられた答えは、OP（と私）がすでに知っていた（n回の操作はlog n回行った）ことを単に再表示しましたが、唯一の重要な部分に光沢がありました。この回答は、ログ用語が実際にどこから来ているのかを簡単かつ素敵に説明しています。 –

それは非常に明確な答えのおかげです。 – huseyin

これは最高の説明です – huseyin

これは必ずしもn（log n）ではありません。選んだピボットがおおよそ中間にあるのは演奏時間です。最悪の場合、ピボットとして最小または最大の要素を選択すると、時刻はO（n^2）になります。

'n log n'を視覚化するには、ピボットを並べ替える配列内のすべての要素の平均に最も近い要素と見なすことができます。これは、アレイをほぼ同じ長さの2つの部分に分割します。これらの両方でクイックソート手順を適用します。

各ステップで、配列の長さを半分にするので、長さ= 1に達するまでログn（基底2）時間、つまり1要素のソートされた配列になります。

出典

2012-05-03 05:28:34

あなたは正しいですが、平均と中央値を混ぜてはいけません。中央値は、同じ長さ（+ -1）の2つの部分に分割できるようにするものです。 – kvetis

実際には、すべてのN要素の位置（ピボット）を見つける必要がありますが、各要素のlogNは最大です（最初はN、2番目のピボットN/2,3rd N/4）。。ピボットを仮定することが中央要素です）

出典

2016-02-21 05:27:43 Prdp

なぜQuickSortがn log nなのかを直感的に説明できますか？

答えて

関連する問題