プログラマーにしか解けない！ #実行時間クイズ

計算回数は 1 億回程度です。家庭用コンピュータでは 1 秒当たり 1 億～ 10 億回程度の計算ができるので、「0.351 秒」と考えるのが妥当です。

このプログラムの計算量は O(N log N) なので、およそ 2 億回程度の計算を行います。しかし、単純な足し算しか行っておらず定数倍が軽いので、実行速度は 1 秒に 10 億回程度と考えて「0.113 秒」と考えるのが妥当です。

このプログラムの計算量は O(2^N×N) なので、およそ 200 億回程度の計算を行います。したがって、「10 秒以上」と考えるのが妥当です。

cout による出力（特に endl）は非常に遅く、「1.299 秒」が正解です。競技プログラミングなどで高速な入出力を行いたい場合は scanf/printf などを使いましょう。

このプログラムはフィボナッチ数を出力するプログラムであり、計算量は O(1.62^N) 程度です。したがって、1～2 億回の計算を行っていると推測できます。定数倍は比較的軽いので、「0.370 秒」と答えるのが妥当です。

N 以下の素数を出力するプログラムです。一見 N^2 回程度の計算を行っているように見えますが、i が 2 で割り切れる場合 1 回でループが終了しているため、全体では 4.5 億回程度しかループしていません。定数倍は比較的軽いので、実行速度は 1 秒に 5 億回程度と考え「1.106 秒」と答えるのが妥当です。

一見 N^2 回の計算を行っているように見えますが、非常に単純なプログラムは C++ が内部で勝手に最適化を行ってくれる場合があり、処理が単純化されてしまいます。したがって、答えは「0.009 秒」です。AtCoder のコードテストで実際に調べてみましょう。

このプログラムの計算量は O(N log N) ですが、std::map は定数倍がかなり重いため「10 秒以上」が正解となります。厳密にはおよそ 11 秒程度です。AtCoder のコードテストで実際に調べてみましょう。

std::sort 関数は計算量 O(N log N) です。正確に実行時間を当てるのは慣れないと難しいですね。

このプログラムの計算量は O(N×bitsetのサイズ) ですが、bitset の定数倍は 1/64 であるため極めて高速に動作します。答えは「2.076 秒」です。それにしてもなかなか速いですね。