19/12/29 21:33:41.90 wJ/DeyFk.net
>>474
そりゃ、例の数列では要素数が少なくてアルゴリズムの差が出にくいからだろ。
「効率よく」とわざわざ書いてある問題なんだから、もっと大きなデータを与えた
場合も想定して答えるのが普通。
例えば、100万から1までの連番の後に2から50万までの連番が続く数列を与えれば
アルゴリズム間の違いは歴然。
Rで二分探索、min関数、sort関数で求めたときの1回あたり平均実行時間を計測すると、
0.132, 2.08, 55.2ミリ秒で桁が違う (PCでは二分探索はもう少し速かった)。
計算量オーダーがO(log n), O(n), O(n log n)だから当たり前だが。
URLﾘﾝｸ(ideone.com)
C++の>>468に同じデータを与えると108ミリ秒かかり、何とRのsort関数より遅い。
Rの関数はCで書かれているものが多いから、この差はつまりはCとC++のSTLの
性能差によるものだろう。
URLﾘﾝｸ(ideone.com)