ソートされていないリスト内の要素を見つける最も効率的な方法は何ですか？

Question

配列内にソートされていないリストがあれば、必ずxより小さい要素の数を見つけるのに少なくとも線形時間がかかりますか？もしそうなら、なぜですか？

Answer 1

はい、すべての数値を少なくとも1回調べて、指定されたしきい値より小さいかどうかを確認する必要があります。数字がソートされていない場合は、それらについて推論できるものは何もありません。

Answer 2

はい、少なくとも線形時間が必要です。要素がチェックされずにxより小さいかどうかを知る方法はないので、すべての要素を一度チェックする必要があります。

最初にソートした場合、要素がxより大きいとすぐに停止することができます。

Answer 3

無制限の数のプロセッサを許可している場合は、ほぼ一定の時間内に問題を解決することができます。結果を連結するのは簡単です：固定サイズのチャンクでアレイを分割し、各チャンクを別々のプロセッサで処理します。

私たちは、私はあなたが線形時間が必要でしょうね、単一のプロセッサについて話している場合：

• あなたはそれぞれの要素を検査する必要があり、それが収まる場合述語が結果にそれを置きます。
• ソートなどは、もう一度各要素を少なくとも1回は検査する必要があるため、役に立ちません。