東大ニート

東大卒のニートが勉強したことをメモするブログ

<アルゴリズム>時間計算量

プログラミングコンテストの問題を解いていると、しばしば「TLE」と判定されてしまうことがあります。これは「Time Limit Exceeded」の略で時間制限を超えてしまったということを意味しています。

今回は、実行時間に大きく関係する「時間計算量」についてメモします。

提出する前に、時間制限を超えないか自分で判断できれば、スコアが上がりやすいですもんね。

領域計算量や平均計算量についても今度調べなきゃですが…。

 以下の本とサイトを参考にさせていただきました。

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

 

catupper.hatenablog.com

 

そもそも計算量とは

そもそも計算量とは、あるアルゴリズムを実行する時に、必要となる資源(時間や記憶容量など)の量を表す評価指標と言えます。

計算量には「時間計算量」「領域計算量」の2種類があり、
時間計算量はアルゴリズムの実行にどれだけ時間がかかるか、
領域計算量はアルゴリズムの実行にどれだけ記憶領域が必要か、
表しています。

また、時間計算量の中でも、最も時間がかかる場合の時間計算量を「最大時間計算量」、すべての入力データに対する時間計算量の平均値を「平均時間計算量」と言います。

時間計算量とは

表記

時間計算量の表記にはオーダー記法が用いられます。

これはO(nlogn)やO(n^2)のように表し、サイズ「n」の入力データが渡された時に、どの程度の時間がかかるのか表しています。

例えばO(n^2)の時間計算量となるアルゴリズムに1000個の入力データを渡すと、
n^2 = 1000 * 1000 = 1,000,000 で、O(10^6)となります。

目安

だいたいの目安としてO(10^7) 〜 O(10^8) が1秒のようです。

計算内容にもよるので、一概には言えないと思いますが、最大時間計算量がO(10^7)でおさまっているかチェックするのが一つの目安でしょう。

計算方法

例えば1つのデータに対し、1000回の処理が必要になるアルゴリズムがあったとします。そこにサイズ「n」のデータを渡した場合、O(n * 10^3)となります。

1つのデータに対し、n + 10回の処理が必要となるアルゴリズムがあった場合、時間計算量はO(n^2 + 10 * n)となりますが、nが大きくなった時、n^2に対し、10 * nは非常に小さくなるので、10 * nは無視してO(n^2)と表記されます。

nの最大次数にのみ注目すればいいということですね。

 

今回のメモは以上となります。各アルゴリズムのオーダーがどれくらいになるかも書きたいので、順次追記していきます。