4

対数時間 ( O(logn) ) でソートされていない配列の最小値を見つけるためのアルゴリズム的アプローチはありますか? それとも線形時間でのみ可能ですか？並行したくない。

ありがとう

マイケル

4

6 に答える 6

16

リストがソートされていない場合、検索は少なくとも線形である必要があります。まだ見ていないものは、すでに見たものよりも少ない可能性があるため、各項目を少なくとも 1 回は確認する必要があります。

于 2011-03-24T15:25:57.117 に答える
2

並列化しても、一般的には役に立ちません。nを超えるプロセッサがあり、データのロードにかかる時間（O（n））をカウントしない場合は、はい、対数時間で実行できます。しかし、たとえば、プロセッサごとに10個の番号があるとします。ある程度の時間がかかります。ここで、プロセッサごとに20個の数値にします。各プロセッサは、互いの結果を並行して比較する前に、その数値を処理するのに2倍の時間がかかります。O（n）+ O（log n）= O（n）。

于 2011-03-26T01:11:23.500 に答える
1

lg nステップでは lg n要素しか検査できず、並べ替えられていないため、値は配列内の他の値に関する情報を持たないため、線形時間ではありません。

于 2011-03-24T15:25:55.293 に答える
0

線形ではありませんが、何らかの変更されたクイックソートを使用すると、要素が 10 未満の場合は線形よりも高速になる可能性があります。配列内のアイテムが10未満であることを疑っています:)

それを達成するもう 1 つの方法は、SSE 命令の世界に没頭することです。

役立つ可能性がある 1 つの OPCODE は、一度に 4 つのスカラーを並行して比較する CMPLEPS です。

並列コードでそれを行う気がない場合は、SSE アセンブリ命令を使用するかどうかを真剣に疑っています。

于 2011-03-24T16:12:30.010 に答える
0

最小値のことですか？

それは線形です-配列を反復処理し、最も知られていない要素の位置（または値自体）を保存し、すべての要素をそれと比較します。代わりにそれを保存する下の要素です。最後に、最小要素の位置 (または値) があります。

C++0x で短い例を作成しました。

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
   std::vector<int> array({5, 3, 2, 7, 5, 1, 9});

   int min = array[0];

   std::for_each(array.cbegin(), array.cend(), [&min] (const int cur) {
      min = std::min(cur, min);
   });

   std::cout << min;
}

Ideoneで実行できます

于 2011-03-24T15:26:30.413 に答える