計算量の話
中西 渉 ∗
2022 年 12 月 28 日

1

はじめに

1.1 概要コンピュータは人間と比べてはるかに高速の

2

計算量

2.1

時間計算量・空間計算量

コンピュータである処理が実行できるかを考計算を行うが，だからといってどんな計算でもえるときに，考えるのは次の事柄である。

できるというものではない。非常に多くのデー• どれだけの時間がかかるか

タや巨大な数値を扱うにはそれ相応の時間がか• どれだけのメモリを使うかかるものだ。この講座では時間のかかる処理を実感・比較することによって，計算量の感覚を前者を時間計算量，後者を空間計算量という身につけることを目標とする。

が，ここでは時間計算量についてだけ考えるこ

1.2 準備とにする（以下，単に計算量というときには時間計算量を指す）。

プログラミング環境は授業と同じように2.2

Spyder を使って Python で行うものとする。使

実行時間の計測用するプロジェクトは筆者のサイトに置いてあ

時間計算量を考えるためには，プログラムのる。Web ブラウザで https://watayan.net の実行時間を計測しなくてはいけない。しかし手「過去の発表資料」のページの「計算量の話」作業でやりたくはないので time モジュールをのところにある「プロジェクト」のリンクをク使うことにする。time.perf_counter() といリックし，「プログラムで開く (unzip)」を選ん

う関数を処理の前と後で呼び出して，その差をで OK を押すとホームに展開される。そのあ計算することで実行時間を計測することにしよとは Spyder のメニューの「プロジェクト」→う。たとえば例 1 のようにすればいい。

例1「プロジェクトを開く」で，自分のホームにあimport timeる「計算量の話」のディレクトリを選択すればこのプロジェクトが開かれる。example??.py

t1 = time.perf_counter()（何らかの処理）t2 = time.perf_counter()print(t2 - t1)
は以下の例??のプログラムである。
∗

名古屋高等学校1しかし，このあとは「何らかの処理」に注目したいので，それがプログラムの途中にあるのはわかりにくい。そこで例 2 のようなプログラムにして，N が入力されたあと f(N) の実行にかかる時間を計測することにする。例 2 では f(N) の中身は None だけであるが，これを計算量を考えたいプログラムに書き換えればいい1）。なお，最後の行にある表示がごちゃごちゃしているのは，桁数を統一して見やすくするためである（10 桁のうち小数部分が 6 桁という指定）。


例2

def f(N):count = 0
for i in range(N):for j in range(N):count += 1


例5




def f(N):count = 0
for i in range(N):for j in range(N):for k in range(N):count += 1



表1import timeN

def f(N):None100

N = int(input())
t1 = time.perf_counter()f(N)t2 = time.perf_counter()print("{:10.6f}".format(t2 - t1))


例4

実行時間の比較

例2

例3

例4

例5100010000100000

表 1 の実行時間を比較しよう。表 3 は N が2.3 オーダー記法

1 桁増えると実行時間も 1 桁増えるくらいではないだろうか。これは次のように考えることが入力する N の値によって実行時間はどのように変化するだろうか。例 2〜例 5 のプログラ

できる：

ムについて，実際に実行して 100,1000,…,100000

N 回の繰り返しだから，i が増えるのが Nを入力し，実行時間を後の表 1 に記録しなさ回，count が増えるのが N 回で変数の値い。ただし例 5 は 1000 までにとどめておくのが増えるのが 2N 回行われる。実行時間はが良い2）。

そのような処理の回数におよそ比例するだ

なお，count += 1 は count = count + 1 とろう。

同じ意味で，変数名を 2 回書かなくてもいいの

このようなとき，実行時間は N にだいたい比でよく使われる記法である。

例3

例するということで O(N ) と表される（係数は比例定数に含まれるので書かない）。同様に表

def f(N):count = 0
for i in range(N):count += 1


4 は O(N 2 )，表 5 は O(N 3 ) となる。例 2 については，実行時間が N の影響を受けないということで O(1) と表される。

実用的なプログラムを作るときには，想定さ

1） None は何もしないという命令。
2） 筆者の PC では 10000 で数時間，100000 で数百日かかる見込み。

れる N の上限と，それに応じた計算量の見積もりが必要である。
2

ちなみに教科書ではこれに加えて3具体例• 2 で割り切れれば素数でない√• 2 で割り切れなければ 3〜 N までの奇数

3.1 素数判定

だけで割ればいい

教科書には素数判定のプログラムが掲載されということで繰り返しの回数はおよそ半分にな√るのだが，計算量は O( N ) のままである。

例8ていた。あれはそれなりにややこしいアルゴリズムになっているので，もっとも素朴なものか

import mathら始めてだんだん近いものにしていく。
一番素朴な考え方は例 6 のように 2 から

def f(N):if N == 1:
return 0の関数は N が素数ならば 1，そうでなければ 0s = int(math.sqrt(N))
flag = 1を返す関数とし，返す値を flag としている。
for i in range(2, s + 1):
if N % i == 0:
これは繰り返し回数が N − 2 であるから，計算
flag = 0return flag
量は O(N ) である。
例6
例 6 →例 7 →例 8 とプログラムを改良してきdef f(N):たわけだが，計算量から考えると例 6 →例 7 はif N == 1:
return 0
どちらも O(N ) だから大したことはなくて，例flag = 1√
for i in range(2, N):
7 →例 8 は O( N ) になったから大したものだ
if N % i == 0:
flag = 0ということになる。例 6 →例 7 も実行時間はおreturn flag
よそ半分にはなっているわけだが，N が 100 倍になればどちらも 100 倍，10000 倍になればど
次に考えるのは，N − 1 まで割らなくても N
N − 1 までで割ってみるというものだろう。こ2

ちらも 10000 倍である。一方例 8 は N が 100までで十分だというものだろう。このプログラ
ムは例 7 のようになり，例 6 のおよそ半分の実倍になれば実行時間は 10 倍，10000 倍でも 100行時間になるが，計算量は O(N ) のままだ。

例7倍なのだから「桁違い」の差がある。
 余談：例 8 は math.sqrt を用いたが，次のよ
うに while を使ったループにすればその必要√はなくなる。計算量はやはり O( N ) である。


例9def f(N):if N == 1:
return 0
flag = 1
for i in range(2, N // 2 + 1):
if N % i == 0:
flag = 0
return flag√N
実は 2 まで割る必要はなくて， N で十分

def f(N):if N == 1:
return 0
flag = 1
i = 2while i * i <= N:
if N % i == 0:
flag = 0i += 1
return flag

だったりする。そうするとプログラムは例 8 の√ようになり，計算量は O( N ) となる。

3

3.2 数当てゲーム

def f(N):a = random.randint(1, N)
b = 1
while a != b:b += 1

1 から N までの乱数を発生させ，少ない質問回数でそれを当てるというゲームを考える。
ただし質問は Yes か No で答えられるものだけ

(3) は二分探索といい，例 12 のように少しやだ。作戦として次の 3 つを考えたが，効率がいやこしくなる。
いのはどれだろう。
(1) 当てずっぽうに数を言って，偶然当たった

例 12

def f(N):a = random.randint(1, N)
l = 1r = N
while l != r:b = (l + r) // 2
if b >= a:r = belse:l = b + 1
ら終了
(2) 1 から小さい順に当たりかどうかを尋ねて，当たったら終了(3) まず l = 1，r = N とし，次の操作を繰り返すa) l = r ならその値が当たりなので終了b) b = b(l + r)/2c とする



例 113）

例 10〜例 12 についても実行時間を比較して表c) b が当たり以上なら r = b，そうでない2 にまとめてみよう。

なら l = b + 1 として a) に戻る。

表2

これらの実行時間を 1 回だけ計算するだけでNは偶然によるものが大きいので，100 回繰り返実行時間の比較

例 10

例 11

例 12100すことにする（例 10〜例 12 は例 2 と違って，1000

f(N) を 100 回繰り返すようになっている）。

10000

また，乱数を使うために random モジュールを100000

import しているのだが，プリントでは省略する。使われている random.randint(1, N) は 1
以上 N 以下の整数の乱数を返す関数である4）。
(1) の「当てずっぽう」だとこうなる。

例 10
def f(N):a = random.randint(1, N)
while a != random.randint(1, N):None
1 から順に尋ねる (2) は線形探索といい，プ

例 10，例 11 はともに O(N ) であるが，例 11の方が若干効率がいい（運次第では例 10 が勝ることもあるかもしれないが）。一方，例 12 はかなり効率がいいらしく，例 10 や例 11 との差は N が大きくなればなるほど大きくなる。このしくみについて少し考察してみよう。

線形探索では 1 回で見つかることもあれば N回で見つかる最悪のケースもある。平均すればログラムは例 11 のようになるだろう。

およそ N2 回なので，計算量は O(N ) になる。
二分探索における繰り返しの所要回数を x とすると，およそ 2x = N となる。というのはこ

3） bxc は x の小数部分切り捨て。
4） range(1, N) と違い，N を含むことに注意。

ういうことだ。
4• N = 2 のときは 1 回尋ねればわかるからのままプログラムにして例 13 のように書くこ1 回。とができる。このように関数の内部で自分自身• N = 4 のときは 1 回尋ねれば (1) になるか
ら 2 回。
• N = 8 のときは 1 回尋ねれば (2) になるか
ら 3 回。
…
数学 II で習うことだが，2x = N となる x をを呼び出すことを再帰という。
例 13

def f(N):if N < 2:
return 1
else:
return f(N - 1) + f(N - 2)


これも実行時間を計測してみよう（プログラlog2 N と表す。つまり例 12 は O(log2 N ) といムは f (N ) の値も表示するようになっている）。

うことで，格段に効率がいい5）。素数判定で出√てきた O( N ) は O(N ) と比べて桁数がおよそただ，表 3 は N が 900 まで書いてあるが，例13 は 40 まででやめておいたほうがいい。

半分であるが，O(log2 N ) はほぼ N の桁数に比√例する。N の桁数を 10000 倍にすると N の桁数はおよそ 5000 倍になるが，log2 N の桁数Nは 4 つ増えるだけである。

10表3

実行時間の比較

例 13

例 14

例 15203.3 フィボナッチ数列

3040数列は数学でまだ学習していないので，ここ50では次のような関数を考えることにする。

100• f (0) = 1500

• f (1) = 1900

• n = 2 のとき f (n) = f (n − 1) + f (n − 2)
3 つめの条件によってたかだか N = 40 でどうしてこんなに時間がかかってしまうのだろう。そこで例として，

f (2) = f (1) + f (0) = 1 + 1 = 2f (5) = 8 を計算する手間を考えてみる。

f (3) = f (2) + f (1) = 2 + 1 = 3f (5) = f (4) + f (3)f (4) = f (3) + f (2) = 3 + 2 = 5= f (3) + f (2) + f (2) + f (1)f (5) = f (4) + f (3) = 5 + 3 = 8= f (2) + f (1) + f (1) + f (0) + f (1) + f (0) + f (1)...

= f (1) + f (0) + f (1) + f (1) + f (0) + f (1) + f (0) + f (1)というようにどんどん先まで計算していくこと
数学なら f (2) + f (2) = 2f (2) として計算量をができる。

減らすのだが，プログラムでは f (4) を計算しこれに対応する f(N) は上に書いたことをそているときの f (2) と f (3) を計算しているとき
5） log2 の 2 を「底」というが，底が変わっても log の値は定数倍しか違わないので，普通は底を省略してO(log N ) という。の f (2) は別にやっているので，それぞれの分の手数がかかってしまう。その結果，f (5) の値5と同じ個数の 1（つまり f (1) と f (0)）にまで分めに Python の「辞書」という機能を使う。こ解されてしまう（図 1 参照）。つまり f (N ) をれは計算するには f (N ) の値と同じくらいの回数の{キー 1:値 1, キー 2:値 2, キー 3:値 3,...}処理が必要になる。正確には(√ N +1 
√ N +1 )1
1+ 51− 5f (N ) = √−225という構文で表されるデータで，キーに対応す√ N
1+ 52

る値は「辞書名 [キー]」の形式で参照したり代入したりすることができる。例 15 では関数f の中に f.dict という辞書を作っておいて，であ

そこに既に計算した f (N ) の値を入れておくこる6）。そのため N が 10 増えると実行時間はおとにした。f(N) は，N が f.dict のキーにあれなので，f (N ) の計算量は Oよそ 123 倍になる。例 13 を N = 40 まででやば7）計算せずに f.dict[N] の値を返し，キーにめておいた方がいいといったのはそういうこなければ f (N − 1) + f (N − 2) で計算する（ことだ。の値は f.dict にも保存する）というプログラムになっている。
f(5)
f(4)
f(3)

f(2)

f(1)

f(3)
f(2)

f(1)

f(2)

f(1)

f(0)

def f(N):if N in f.dict:return f.dict[N]a = f(N - 1) + f(N - 2)
f.dict[N] = a
return af.dict = {0:1, 1:1}
f(1)

f(1)

f(0)

f(0)

図 1 f (5) の計算

にくらべてはるかに高速である。例 13 は N の指数関数であり，N が増えればかかる時間が最初に行ったように，f (2)，f (3)，f (4)，…と急速に増えてしまう。

いうように順に計算していくというものだ。こdef f(N):if N < 2:
return 1
else:
a = 1
b = 1
for i in range(N - 1):
c = a + b
a = bb = c
return c

例 14 と例 15 はともに O(N ) であるから，例 13

計算量を減らす工夫を 2 つ紹介する。一つはれはループを使えばいい。

例 14

例 15

一般的に O(N ) や O(N 2 ) のようなものは多N項式時間，O(2 ) のようなものは指数関数時√間といわれる。 N や log N は多項式ではない√が，増え方が N よりも緩やかなので O( N ) やO(log N )，O(N log N ) なども多項式時間に含まれる。
N がある程度大きいときには指数関数時間のアルゴリズムが使いものにならないことがよくある（逆に N が小さいときに限っては有効なこともある）。多項式時間は指数関数時間にもう一つは，すでに計算した値は覚えておい比べれば小さいことが多いが，さらにいえば次て，2 回以上計算しないというものだ。そのた数が小さいに越したことはない。

6） およそ O(1.62N )。

7） N in f.dict はこれを調べている。

6

を公開鍵の一部として使う。復号に用いられる

4

おわりに秘密鍵は p，q と公開鍵で作られるのだが，公開されている n を素因数分解して p と q を求めることができれば，それによって秘密鍵を生成4.1 ソートできるので盗聴者が復号できてしまう。しかしソートの計算量は（比較ソートに限れば）大2

巨大な数の素因数分解を（log n の）多項式時間8）抵のものは O(N log N )〜O(N ) である 。たで行うアルゴリズムは知られていないので，pとえば簡単に実装できるバブルソートや挿入や q を求めることは現実的な時間ではできず，ソート，選択ソートは O(N ) であるから，速RSA 暗号方式は安全であると考えられている。

度が要求されるときはヒープソートやクイックもっとも，量子コンピュータが実用化されればソートなどが用いられる。しかしクイックソー可能だという考えもあるのだが。

トは平均すれば O(N log N ) なのだが，最初の4.42並び順が最悪の場合には O(N 2 ) になってしま

競技プログラミング

AtCoder や情報オリンピックのような競技プうので注意が必要である。

ログラミングでは，計算量の見積もりが重要で4.2 素数判定ある。たとえば次のような問題を考える9）。
√
素数判定については O(N ) や O( N ) である



非負正数列 A = (a1 , a2 , . . . , aN ) が与えらものを扱ったが，普通このような問題では Nれます。A の（添字が異なる）K 個の項でなく log N（大雑把にいえば N の桁数）の式の和として考えられる非負整数の集合をでどう表されるかを考える。N = 2log2 N ある√√√ log N
いは N = 2 2 なので，O(N ) や O( N )S とします。S に含まれる D の倍数の最大値を求めてください。ただし S に D のはその意味では指数関数時間がかかる低速なア倍数が含まれない場合，代わりに −1 と出ルゴリズムなのである。

力してください。制約条件は以下の通り

2002 年にインド工科大学で，log N の多項式です。

時間で素数判定ができることが証明された。その論文 “PRIMES is in P” が公開されたときに• 1 5 K 5 N 5 100

は大きい話題となったことを覚えている。しか• 1 5 D 5 100

し，これで素数判定が速くなったというわけで• 0 5 ai 5 109

はない（多項式の次数が高すぎるため）。



これを解くのに K 個の項の組み合わせすべて4.3 暗号の話を調べようとすると，N CK 通りを調べること計算量は小さければ小さいほどいい…と考えになる。N を固定したときの N CK の最大値がちであるが，場合によっては計算量が大きく

N Cb N c は N の指数関数に近いので，制限時間なくてはいけないものもある。例えば RSA 暗内には終了しない。どういうアルゴリズムでそ号方式では 2 つの大きい素数 p，q の積 n = pq

れを回避するかが競技プログラミングの醍醐味2だと考えている。
8） 比較ソートは O(N log N ) が下限。

9） AtCoder Beginner Contest 281 D 問題。

7