0

重複の可能性:
比較数が最小の配列で 2 番目に大きい要素を見つける

O(n+logn) 時間で最大数と ​​2 番目に大きな数を検索する方法を教えてください。前もって感謝します。

よろしく、 ピディグ

4

3 に答える 3

7

O(n+logn) = O(n)であり、リストを 2 回繰り返すことに注意してくださいO(n)。

  1. 一度反復して最大値を見つけ、それを削除/マークします。
  2. 次に、新しい最大値 (2 番目に大きい要素) を見つけるために 2 回目の反復を行います。

配列に対して一定回数反復するため、アルゴリズムはO(n).

汎用の最大要素の場合:この回答で説明されているように、k最小ヒープO(nlogk)または選択アルゴリズムを使用して実行できますが、2 つの最大要素の場合、これらの方法はやり過ぎです。O(n)

于 2012-05-31T14:38:18.177 に答える
3

n + log(n) - 2 回の比較を意味していると思います。

これがその方法です。

要素を 2 つのグループで比較します。つまり、それぞれ 2 つの要素からなる n/2 グループを作成します。

このように n/4、n/8、n/16 などと続けて、最初の (最大の) 要素を取得します。

次に大きい要素は、このメソッドの最初の要素の敗者の中になければなりません。したがって、これについてさらに log(n) 回の比較が行われます。

正確には、これには n + log(n) - 2 回の比較が必要です。

于 2012-05-31T14:51:15.843 に答える
1

あなたは実際にそれをO(n)時間内に行うことができます:選択アルゴリズム

于 2012-05-31T14:38:51.833 に答える