17

O（log n）時間でソートされていない配列の最大値を見つけるアルゴリズムは存在しますか？

4

9 に答える 9

25

この質問はよく聞かれます（これは人気のあるCSの宿題の質問か何かですか？）、答えは常に同じです：いいえ。

数学的に考えてください。配列がソートされていない限り、動作を与えるために「半分にカット」するものは何もありませんlog(n)。

より詳細な議論については、質問のコメントを読んでください（とにかく質問の範囲から外れている可能性があります）。

于 2012-09-15T20:33:06.197 に答える
10

これを考慮してください：すべての要素を訪問せずに、あなたが訪問していないいくつかの要素があなたがこれまでに見つけた最大のものより大きくないことをどうやって知るのですか？

于 2012-09-15T20:38:13.970 に答える
6

でこれを行うことはできませんO(log(N))。O(N)配列内のすべての項目にアクセスして、それが最大のものであるかどうかを判断する必要があるため、これは最良/最悪/平均のケースです。配列はソートされていないため、コーナーをカットすることはできません。

並列化の場合でも、Big-O記法は CPU の数や各 CPU の周波数を気にしないO(N)ため、これは では実行できません。これは、問題の大まかな見積もりを提供するために、特にこれから抽象化されます。

ジョブの分割に費やされる時間は、順次実行の時間と等しいと見なすことができるため、並列化は無視できます。これは、定数が無視されているためです。以下はすべて同じです。

O(N) = O(Const * N) = O(N / Const) = O(N + Const) = O(N - Const)

一方、実際には、分割統治型の並列アルゴリズムを使用すると、パフォーマンス上の利点が得られるため、実行速度が少し速くなる可能性があります。幸いなことに、Big-Oは、このきめの細かいアルゴリズムの複雑さの分析を扱っていません。

于 2012-09-16T12:25:22.243 に答える
4

番号。少なくとも1回は配列を反復処理する必要があります。

于 2012-09-15T20:31:09.613 に答える
4

いいえ、O（n）です。最悪の場合、アレイのすべてのメンバーを訪問して比較する必要があります。

于 2012-09-15T20:32:13.857 に答える
1

もちろん違います 。まだ他の要素と比較していない要素がまだあるとします。したがって、比較していない要素が最大要素ではないという保証はありません

比較グラフ (要素の頂点と比較のエッジ) に複数のコンポーネントがあるとします。この場合、エッジを配置する必要があります (最大 2 つのコンポーネントの間に最適な方法で)。 n-1 操作を実行する必要があることがわかります。

于 2014-05-13T12:34:27.577 に答える