Chapter 30

時間計算量

ABC085 C - Otoshidama

ABC085 C - Otoshidama を解くことを考えます．

要約すると，「整数 $N, Y$ が与えられるので， $x + y + z = N$ ， $10000x + 5000y + 1000z = Y$ を満たす整数の組 $(x, y, z)$ を探せ」という問題です．

$Y$ と $y$ があるので，以下コード中では $y$ （ $5000$ 円札の枚数）を変数 y で， $Y$ （金額の合計）を変数 sum で表します．

解法 1

$x + y + z = N$ なので， $x, y, z$ は全て $0, 1, 2, \ldots, N$ のいずれかです．よって， 3 重の for 式を書いて $x, y, z$ をそれぞれ $0, 1, 2, \ldots, N$ の範囲で動かせば，その中に答えがあります．これをそのままコードに書くと，次のようになります．

use proconio::input;

fn main() {
    input! {
        n: i32,
        sum: i32,
    }
    for x in 0..=n {
        for y in 0..=n {
            for z in 0..=n {
                if x + y + z == n && x * 10000 + y * 5000 + z * 1000 == sum {
                    println!("{} {} {}", x, y, z);
                    return;
                }
            }
        }
    }
    println!("-1 -1 -1");
}

これを実際に提出したものがこれです． AC の代わりに TLE と表示されています．

AC や WA ， TLE といった表示の意味はこのページに書いてあります．これを見ると， TLE は「問題で指定された実行時間以内にプログラムが終了しなかった」という意味だと分かります．今回の場合，問題文の上部に「実行時間制限: 2 sec 」と書いてあるので，提出したコードは 2 秒以内に終了しなかったということになります．よって，コードを書き換えてプログラムをもっと高速にしなければなりません．

解法 2

$x + y + z = N$ という条件を見ると， $x$ ， $y$ を決めたとき， $z$ の値として考えられるのは $z = N - x - y$ しかありません．よって，

$x, y$ をそれぞれ $0, 1, 2, \ldots, N$ の範囲で動かす
$z = N - x - y$ として， $10000x + 5000y + 1000z = Y$ が成り立っているか調べる

というやり方で答えを求めることもできます．ただし， $z < 0$ となる場合があるので除外します．

この解法で実際にコードを書き，提出してみてください．正しく書くことができれば，この提出のように AC となるはずです．

アルゴリズム

ある処理の内容を形式的な手続きとして言い表したものを，アルゴリズムといいます．

解法 1 のアルゴリズムは，

$x, y, z$ をそれぞれ $0, 1, 2, \ldots, N$ の範囲で動かす．
$x + y + z = N$ ， $10000x + 5000y + 1000z = Y$ が成り立っていれば， $x, y, z$ の値を出力して終了する．
$x, y, z$ が全ての範囲を動いても終了しなかったら， -1 -1 -1 と出力する．

のように言い表され，解法 2 のアルゴリズムは

$x, y$ をそれぞれ $0, 1, 2, \ldots, N$ の範囲で動かす．
$z = N - x - y$ としたときに $z \geq 0$ ， $10000x + 5000y + 1000z = Y$ が成り立っていれば， $x, y, z$ の値を出力して終了する．
$x, y$ が全ての範囲を動いても終了しなかったら， -1 -1 -1 と出力する．

のように言い表されます．解法 1 が TLE ，解法 2 が AC だったということは，解法 1 のアルゴリズムより解法 2 のアルゴリズムの方が高速だということを意味します．では，後者は前者よりどのくらい速いのでしょうか？これを考えるための道具となるのが，時間計算量の概念です．

時間計算量

四則演算やビット演算，数同士の比較，値のコピーといった一つ一つの処理がプログラムの開始から終了までの間に行われる回数を，入力 $N$ や $Y$ の関数として表したものを，時間計算量といいます．ここでは $Y$ を省き， $N$ の関数として時間計算量を考えることにします（余裕がある人は， $Y$ を加えた 2 変数関数についても考えてみると良いと思います）．

たとえば，解法 1 のアルゴリズムでは，各ループの中で $x + y + z = N$ と $10000x + 5000y + 1000z = Y$ を確かめるために何度かの足し算と掛け算と比較が行われます．一回のループにおける計算の回数を $f_1(N)$ とすると，短絡評価を行わない場合でも足し算が 4 回，掛け算が 3 回，比較が 2 回なのでせいぜい $f_1(N) \leq 9$ と考えられます．

$x, y, z$ のそれぞれが $0, 1, 2, \ldots, N$ の範囲を動くと，このループは $(N + 1)^3$ 回繰り返されます．全体の時間計算量を $f_2(N)$ とすると， $f_2(N) = (N + 1)^3 f_1(N) \leq 9(N + 1)^3$ です．

解法 2 のアルゴリズムでは，各ループの中で $z = N - x - y$ が計算され， $z \geq 0$ と $10000x + 5000y + 1000z = Y$ が確かめられます．一回のループにおける計算の回数を $f_3(N)$ とすると，短絡評価を行わない場合でも引き算が 2 回，掛け算が 3 回，足し算が 2 回，比較が 2 回なのでせいぜい $f_3(N) \leq 9$ と考えられます．

しかし今回は $x, y$ の 2 つだけが $0, 1, 2, \ldots, N$ の範囲を動くので，ループの回数は $(N + 1)^2$ 回です．よって，このアルゴリズム全体の時間計算量を $f_4(N)$ とすると， $f_4(N) = (N + 1)^2 f_3(N) \leq 9(N + 1)^2$ です．

問題を見ると，制約のところに $N \leq 2000$ と書かれています．プログラムが TLE になるかどうか考えるときは，時間計算量が最大となるような $N$ について考えます． $f_2(N)$ が最大となるのは $N = 2000$ のときで，このとき $f_2(2000) \leq 9 \cdot 2001^3 = 7.2 \times 10^{10}$ です．一方， $f_4(N)$ が最大となるのも $N = 2000$ のときですが，こちらは $f_4(2000) \leq 9\cdot 2001^2 = 3.6 \times 10^7$ となります．解法 1 の実行時間は 2 秒より長く，解法 2 の実行時間は 2 秒より短かったので， 2 秒の間に可能な計算の回数は $7.2 \times 10^{10}$ より少なく， $3.6\times10^7$ より多そうだということが分かります．

また，この記事では目安として

$1$ 秒間で処理できる for 文ループの回数は、 $10^8=100,000,000$ 回程度

と書かれています．この目安は年々変化しているようです．

「計算の回数」を表す時間計算量に対し，「使用するメモリの量」を表すのが空間計算量です．たとえばこの記事で扱った問題には「メモリ制限: 256 MB 」という制限も書かれています． 256 メガバイトは $256 \times 10^6 = 2.56\times 10^8$ バイトなので，たとえば長さが $6.4\times10^7$ であるような Vec<i32> 型ベクタを作ろうとするとこの制限に引っかかることになります．メモリ制限を超えてしまった場合，提出のステータスは TLE の代わりに MLE となります．

ランダウの O

コンテスト中の限られた時間の中でアルゴリズムの時間計算量を考えるのは大変です．そこで，ここではランダウの $O$ を用いた時間計算量の大雑把な評価の仕方も紹介します．

$N$ の関数 $f(N)$ と $g(N)$ があったとき，次を満たすような定数 $c$ と $n$ を見つけることができるなら， $f(N) = O(g(N))$ と書きます．

$N = n, n + 1, n + 2, n + 3, \ldots$ の全てについて， $|f(N)| \leq c\cdot|g(N)|$ が成り立つ．

具体的な例を用いて考えてみましょう． $f(N) = 2N + 5$ ， $g(N) = N$ とします．このとき，条件を満たすような $c$ と $n$ の例として，たとえば $c = 3$ ， $n = 5$ があります．なぜなら， $N = 5, 6, 7, \ldots$ の全てについて， $|2N + 5| \leq 3|N|$ が成り立つからです．よって， $2N + 5 = O(N)$ と書けます．

一方， $f(N) = N^2$ ， $g(N) = N$ とします．このとき，どんな $c$ を考えたとしても，不等式 $|N^2| \leq c\cdot|N|$ は $N$ を大きくするといつか成り立たなくなってしまいます．よって， $N^2 = O(N)$ ではありません．

いくつか練習問題を置いておくので，解いてみてください．

$N = O(N)$ ですか？
答え

はい．具体的には， $c = 1$ ， $n = 1$ とすると $N = 1, 2, 3, \ldots$ の全てについて $|N| \leq |N|$ が成り立ちます．
$2N + 1 = O(N^2)$ ですか？
答え

はい．具体的には， $c = 1$ ， $n = 3$ とすると $N = 3, 4, 5, \ldots$ の全てについて $|2N + 1| \leq |N^2|$ が成り立ちます．
$N = O(2N - 3)$ ですか？
答え

はい．具体的には， $c = 1$ ， $n = 3$ とすると $N = 3, 4, 5, \ldots$ の全てについて $|N| \leq |2N - 3|$ が成り立ちます．
$N = O(1)$ ですか？
答え

いいえ． $c$ をどれだけ大きくしても， $N > c$ なら $|N| \leq c\cdot |1|$ は成り立ちません．
$5 = O(1)$ ですか？
答え

はい． $c = 5$ とすれば， $N$ に関わらず $|5| \leq 5 \cdot |1|$ が成り立ちます．
$a$ を正の定数とします． $f(N) = O(g(N))$ ならば $af(N) = O(g(N))$ ですか？
答え

はい．

$f(N) = O(g(N))$ より，ある $c$ と $n$ が存在して， $N = n, n + 1, n + 2, \ldots$ の全てについて $|f(N)| \leq c\cdot|g(N)|$ が成り立ちます．

ここで $c' = ac$ とおくと， $N = n, n + 1, n + 2, \ldots$ の全てについて
$\begin{aligned} |af(N)| &= a \cdot |f(N)| \\ &\leq a \cdot c \cdot |g(N)| \\ &= c' \cdot |g(N)| \end{aligned}$
が成り立ちます．こうして，条件を満たす $c'$ と $n$ を見つけることができたので， $af(N) = O(g(N))$ です．
$f(N) = f_1(N) + f_2(N)$ とします． $f_1(N) = O(g(N))$ かつ $f_2(N) = O(g(N))$ ならば $f(N) = O(g(N))$ ですか？
答え

はい．

$f_1(N) = O(g(N))$ より，ある $c_1$ と $n_1$ が存在して， $N = n_1, n_1 + 1, n_1 + 2, \ldots$ の全てについて $|f_1(N)| \leq c_1\cdot|g(N)|$ が成り立ちます．一方， $f_2(N) = O(g(N))$ より，ある $c_2$ と $n_2$ が存在して， $N = n_2, n_2 + 1, n_2 + 2, \ldots$ の全てについて $|f_2(N)| \leq c_2\cdot|g(N)|$ が成り立ちます．

ここで， $c = c_1 + c_2$ とし， $n$ を $n_1$ と $n_2$ のうちの大きい方とします．すると， $N = n, n + 1, n + 2, \ldots$ の全てについて
$\begin{aligned} |f(N)| &= |f_1(N) + f_2(N)| \\ &\leq |f_1(N)| + |f_2(N)| \\ &\leq c_1\cdot|g(N)| + c_2\cdot|g(N)| \\ &= c\cdot|g(N)| \end{aligned}$
が成り立ちます．
$f(N), g(N), h(N)$ があったとき， $f(N) = O(g(N))$ ならば $f(N)h(N) = O(g(N)h(N))$ ですか？
答え

はい．両辺に $|h(N)|$ （ $\geq 0$ ）をかけても不等号の向きは変わらないので， $|f(N)| \leq c\cdot|g(N)|$ が成り立つなら
$\begin{aligned} |f(N)h(N)| &= |f(N)|\cdot|h(N)| \\ &\leq c\cdot|g(N)|\cdot|h(N)| \\ &= c\cdot|g(N)h(N)| \end{aligned}$
です．
整数 $a, b$ について， $0 \leq a \leq b$ ならば $N^a = O(N^b)$ ですか？
答え

はい． $m = b - a$ とすると $m \geq 0$ です．このとき， $m > 0$ なら $N^m$ は単調増加なので $1 = O(N^m)$ です．また $m = 0$ のときも $N^m = 1$ より $1 = O(N^m)$ です．あとは両辺に $N^a$ をかけて $N^a = O(N^b)$ を得ます．
$2N^3 + 5N^2 + N + 10 = O(N^3)$ ですか？
答え

はい． $2N^3 = O(N^3)$ ， $5N^2 = O(N^3)$ ， $N = O(N^3)$ ， $10 = O(N^3)$ より， $2N^3 + 5N^2 + N + 10 = O(N^3)$ です．
$\sqrt{N} = O(N)$ ですか？
答え

はい． $0 \leq a \leq b \Rightarrow N^a = O(N^b)$ は $a, b$ が整数でなくても実数のとき成り立ちます．
$2^N = O(N^{100})$ ですか？
答え

いいえ．どんな $m > 0$ に対しても $2^N = O(N^m)$ は成り立ちません．
$3^N = O(2^N)$ ですか？
答え

いいえ． $a > b > 1$ ならば $a^N = O(b^N)$ は成り立ちません．
$\log_2N = O(\log_3N)$ ですか？
答え

はい． $a > 1, b > 1$ ならば $\log_aN = \log_ab \cdot \log_bN$ より $\log_aN = O(\log_bN)$ が成り立ちます．
$\log{N} = O(\sqrt{N})$ ですか？
答え

はい．どんな $m > 0$ に対しても $\log{N} = O(N^m)$ が成り立ちます．
$N! = O(2^N)$ ですか？
答え

いいえ．もし $N! = O(2^N)$ が成り立つと仮定すると，ある $c$ と $n$ が存在して， $N = n, n + 1, n + 2, \ldots$ の全てについて $N! \leq c2^N$ すなわち $\frac{N!}{2^N} \leq c$ ですが，これは
$\frac{N!}{2^N} = \frac{1}{2}\cdot\frac{2}{2}\cdot\frac{3}{2}\cdot\cdots\cdot\frac{N}{2} \to \infty \quad (N \to \infty)$
であることと矛盾します．
$(N + 1)! = O(N!)$ ですか？
答え

いいえ． $\frac{(N + 1)!}{N!} = N + 1 \to \infty \quad (N \to \infty)$ です．

さて，最初の問題に戻って， 2 つのアルゴリズムの時間計算量 $f_2(N), f_4(N)$ をランダウの $O$ を用いて評価してみます．このとき， $f(N) = O(g(N))$ の $g(N)$ ができるだけ単純な式になるようにします．アルゴリズムの計算量が 1 変数関数 $f(N)$ のとき，たいてい $g(N)$ を $1, N, N^2, N^3, \ldots$ や $\sqrt N$ や $2^N, 3^N$ や $\log N$ ，あるいはこれらの積として表すことができます．

解法 1 のアルゴリズムについては， $f_2(N) \leq 9(N + 1)^3 = 9(N^3 + 3N^2 + 3N + 1)$ なので $f_2(N) = O(N^3)$ です．解法 2 のアルゴリズムについては， $f_4(N) \leq 9(N + 1)^2 = 9(N^2 + 2N + 1)$ なので $f_4(N) = O(N^2)$ です．

$f_2(N) = O(N^3)$ の $N^3$ に $N = 2000$ を代入してみると， $2000^3 = 8\times10^9$ となります．一方， $f_4(N) = O(N^2)$ の $N^2$ に $N = 2000$ を代入すると $2000^2 = 4\times10^6$ となります．

このように単純な式 $g(N)$ を用いて $f(N) = O(g(N))$ という評価を考えたとき， $g(N)$ の最大値が $10^8$ あるいは $10^9$ を超えるようであれば，そのアルゴリズムは TLE になる危険性が高いと言われています．

このようなランダウの $O$ を用いた評価は，ループの回数に着目することで時間計算量 $f(N)$ 自体の評価よりずっと楽に行えることが多いです．たとえば，解法 1 のコードを見ると 3 重のループが書かれており，繰り返しの回数は 3 つとも $N + 1$ です．ここから $f_2(N) = O(N^3)$ であるということが分かります．

もちろん， $f(N) = 50N$ のような場合に $f(N) = O(N)$ と評価をすれば，たとえ $N \leq 10^8$ であったとしても $f(N) = 5 \times 10^9$ で TLE となり得ます． $f(N)$ が $g(N)$ をおおよそ $a$ 倍したものだったとき，定数 $a$ がとても大きい場合に注意が必要です．

一方，アルゴリズムを改善する際に $g(N)$ が変化しないこともありえます．たとえばアルゴリズム 1 の時間計算量 $f_1$ とアルゴリズム 2 の時間計算量 $f_2$ の間に $f_2(N) = \frac1{50}f_1(N)$ くらいの違いがあれば，アルゴリズム 1 で TLE だけれどもアルゴリズム 2 で AC するようなことも考えられます．

最初のうちは，ループの回数を見てランダウの $O$ による評価ができれば困ることはないと思います．