配列の中から最大値を速く求めたい。

Question

配列の中から最大値を求めるのが速い方法を教えてください。
C＋＋を使っていまして、
例えば
int aaa[10]={3,5,2,1,6,7,4,5,9,3}
という配列があったとすると、9を最も速く出せる方法は何でしょうか。（実際には１万個くらいある）
ぱっと思いつくのは先頭から一つずつ比べる方法、つまり最大値を更新したらそれ用の変数（例えばaaamax）を入れ替えていく方法。
次に思いつくのはソートして先頭を取得する方法。
私にはこれくらいしか思いつきません。どちらのほうが速いのでしょうか。
あるいはこれより速い方法をご存じでしたらどうかよろしくお願いします。

Comments

[hanamur]

皆さん、回答ありがとうございました。
いくつか方法を出していただいたので私の場合に速いのはどれかを試してみます。
BAは回答が速かったfanaさんに。
皆さんありがとうございます。

Answer 1

「配列」の中身が何かしらの「最大値を効率良く求めるのに都合の良い形」になっていないのであれば，
全ての要素をチェックしない限り最大値はわからないのだから，全部見るしかない．

単発の探索を考えるなら，単純に全部見るのは O(n) だろうからソートより早い．
ソートが有用なのは，ある時点でソートしたという結果を以降に活かせるような話があるのかどうか次第かと．

Comments

[fana]

最大値なる値が欲しいタイミングで速度が重視されるのであれば，
それ以外のときに最大値を求めて保持しておけばよいのではあるまいか．
その配列の内容を変更する処理において「現在の最大値」を都度更新するとか．

Answer 2

あらかじめ昇順/降順に並んでいるのでもなければ、
最大値を見つけるのは総当たりすなわち要素数に比例した時間:O(N)を要します。

ソートしておけば速いのは事実ですが、ソート自体がO(NlogN)の時間計算量(最短で)ですから。

「ソートされてはいないけど最大値はどれか」が求めるものであるならヒープを作るのがオススメ。
要素の追加に要する時間計算量はO(logN)です。
※ vectorとpush_heap()/pop_heap() を使います。

Answer 3

実験したところ, hanamurさんが挙げてくださったもの以外に速い方法がありました。

#include<iostream>
#include<algorithm>
using namespace std;

int main() {
  int aaa[10]={3,5,2,1,6,7,4,5,9,3};
  cout<<*max_element(aaa,aaa+10)<<endl;
}

algorithm関数を用いてポインタの形で表す方法です。
計算時間を調べると最大値を順に更新する方法では0.72秒, 上のコードでは0.07秒, ソートして先頭の数を出力する方法では1.10秒でした。よって, 定義を使わずmax_elementを使用するのが速いと思います。

Comments

[fana]

それぞれがどんな実装の話なのか，可能であればそのコードも示されると良いのではないかな，と．

> 最大値を順に更新する方法では0.72秒

たかだか１０要素から最大値を見つけるのに 0.7 秒もかかるとは思えないのですが，何か誤記でしょうか？