回答編集履歴
2
加筆
test
CHANGED
@@ -4,4 +4,5 @@
|
|
4
4
|
ソートしておけば速いのは事実ですが、ソート自体がO(NlogN)の時間計算量(最短で)ですから。
|
5
5
|
|
6
6
|
「ソートされてはいないけど最大値はどれか」が求めるものであるならヒープを作るのがオススメ。
|
7
|
+
要素の追加に要する時間計算量はO(logN)です。
|
7
8
|
※ vectorとpush_heap()/pop_heap() を使います。
|
1
追記
test
CHANGED
@@ -2,3 +2,6 @@
|
|
2
2
|
最大値を見つけるのは総当たりすなわち要素数に比例した時間:O(N)を要します。
|
3
3
|
|
4
4
|
ソートしておけば速いのは事実ですが、ソート自体がO(NlogN)の時間計算量(最短で)ですから。
|
5
|
+
|
6
|
+
「ソートされてはいないけど最大値はどれか」が求めるものであるならヒープを作るのがオススメ。
|
7
|
+
※ vectorとpush_heap()/pop_heap() を使います。
|