計算量という考え方
名古屋高等学校 高 1 冬期進学講座
担当：数学科・情報科 中西渉

第 1 章 はじめに
1.1 概要コンピュータは人間と比べてはるかに高速の計算を行うが，だからといってどんな量の計算でもできるというわけではない。巨大なデータや数値の計算には，やはりそれなりの時間がかかってしまう。少しでも高速に処理を済ませた
いために，ハードウェアもソフトウェアも進歩を続けてきた。
しかし，何でも計算が速くできればいいというものではない。たとえば現代の暗号は時間をかければ解けるのだが，そのために途方もない時間が必要になるので暗号としての用が足せている。この場合は逆に計算量が小さくならない保証を求めていることになる。
この講座では，実際に時間のかかる処理を体験・比較することで，計算量を実感することを目標とする。
1.2 準備Web ブラウザで筆者の個人サイトである https://watayan.net の「過去の発表資料」のページの一番上にある「計算量という考え方」の「プログラム一覧のテキスト」を開きなさい。ここに使うプログラムのコードが書いてあるので，打ち込むのが面倒ならここからコピーしなさい。
次に Spyder を起動して，新規ファイルを一つ作りなさい。そこにこれからプログラムを書いていく（あるいはコピーする）ことにする。この講座ではこの 1 つのファイルだけを使い，中身を随時書き換えていく。

1

第 2 章 計算量
2.1 時間計算量・空間計算量

計算量というと主に次の 2 つを考える。
どれだけの時間がかかるかどれだけのメモリを使うか
前者を 時間計算量 ，後者を 空間計算量 という。たとえば 40 人のクラスでばらばらに集めたプリントを，出席番号順に並べるときに次の 2 つの手順を考えてみる。
1. プリントの束を上から順番に見ていって出席番号 1 のプリントを抜き出して，裏向きにして隣に置く。次に同じように出席番号 2 のプリントを抜き出し，出席番号 3 のプリントを抜き出し…これを最後まで繰り返す。
2. 大きい机にプリント 40 枚分のスペースを用意して番号をつける。プリントの束の上から順に番号のところに置いていき，終わったら端から順に集める。
1.の方法は場所を取らないが時間がかかり，逆に 2.の方法は短時間で済むが広い場所が必要になる。この例では，使う場所の広さが空間計算量，時間が時間計算量に相当する。
手順 時間計算量 空間計算量
1. 大小
2. 小大
以下，この講座では時間計算量だけを考えるので，これを単に 計算量 ということにする。
2.2 実行時間の計測

時間計算量を考えるためには，プログラムの実行時間を計測しなくてはいけない。といっても手作業では不正確なので，ここでは time モジュールのperf_counter 関数を用いることにする。これを処理の前と後で呼び出してそ2の差を計算することで，実行時間がわかる。具体的には次のようになる。
import time
t1 = time.perf_counter()（実行時間を計測する処理）
t2 = time.perf_counter()print(t2 - t1)

しかし「実行時間を計測する処理」を今後何度も書き換えることを考えると，それがプログラムの途中にあるのはわかりにくい。そこで次のプログラムで，f(N)の中身だけを書き換えることにしよう（最後の表示がごちゃごちゃしているのは，表示の桁数を揃えるためである）。
import time
import random

このプログラムを入力またはコピーしなさい

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

これを入力（またはコピー）して実行してみなさい。実行すると入力待ちになるので，右下の「コンソール」をクリックして適当な整数を入力しなさい。
入力した数と，実行時間が表示されるはずだ。
今後はこれの f(N)の部分だけを書き換えて実行し，入力した N の値と実行時間の関係について考えていく。

3

2.3 オーダー記法

入力する N の値によって実行時間がどのように変わるかを考えてみる。まずf(N)を書き換えないままで実行し，100，1000，10000，100000 を入力したときの実行時間を次の表に記入しなさい（といっても，N は実行時間に関係しないので，ほとんど同じ数値のはず）。
次に f(N)のところだけを以下の例 1〜例 3 に置き換えて（手作業で書いてもいいし，コピーしてもいい），同様に 100，1000，10000，100000 を入力したときの実行時間をまとめなさい。ただし例 3 については 1000 までにとどめておくこと（筆者の PC では 10000 で数時間，100000 で数百日かかる見込み）。
例 2 の 100000 も数分かかるだろう。
def f(N):count = 0
for i in range(N):count += 1
return count

例1

def f(N):count = 0
for i in range(N):for j in range(N):例2count += 1
return count

例3

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

4

元のまま

N

例1

例2

例31001000
10000×100000×
元のままのプログラムは f(N)の中で何もしていないから，N が増えても実行時間はほぼ変わらないはずだ。一方，例 1 や例 2，例 3 は N が 10 倍になるごとに，実行時間は何倍になっているだろうか。理論上は例 1 は約 10 倍，例 2 は約100 倍，例 3 は約 1000 倍になる。つまり例 1 の実行時間はおよそ N に比例し，
例 2 の実行時間はおよそ N**2 に，例 3 はおよそ N**3 にそれぞれ比例する。実際に計算が行われている回数を大雑把に見積もると次のようになる。
例 1 は i も count も 回ずつ増え，計算が約 回行われる。
例 2 は i が 回増え，そのたびに j も count も 回ずつ増え，計算が回行われる。
例 3 は i が 回増え，そのたびに j も 回ずつ，そのたびに k も countも 回ずつ増え，計算が回行われる。
そこで例 1，例 2，例 3 の計算量をそれぞれ ， ，と表す（係数や最高次でない項は無視する）。このような表現をオーダー記法という。
ちなみに元のままのプログラムは である。
計算量を表す式は多項式ばかりではない。たとえば整数の足し算や引き算の計算量はおよそ桁数に比例するので，計算量はである。なお， は数学 II の「指数関数と対数関数」の単元で出てくるものなので，ここでは簡単に説明する。のときと定義するものであるが， が変化すると は大きく変化するということを逆に考えると， の増え方に比べて の増え方は非常に緩やかである。つまり の増え方は非常に緩やかである，ということだけがわかれば現時点では十分である。他にもとかの計算量が必要なアルゴリズムもあって，このようなものは小さい数でしか計算ができない。
N2NNN

N (1 + 2N ) = N + 2N2NNNN (1 + N (1 + 2N )) = N + N

O(N ) O(N2)2+ 2N

O(N33)

O(1)O(log N )xa= bx = logalogbxbbxlog N

O(25N)O(N !)

第 3 章 具体例
3.1 素数判定・素因数分解

ある整数が素数か素数でないかを判断するアルゴリズムを考える。たとえば
N が素数かどうかを判定するには「2 から N-1 までの整数で割ってみて，どれかで割り切れれば素数でない，最後まで割り切れなかったら素数」と考えると次のようになる（素数なら 1，素数でなければ 0 を返す関数にした）。
素数：例 1

def f(N):if N == 1:
return 0for i in range(2, N):
if N % i == 0:return 0
return 1

これの計算量は である。次のような改良をするとどうだろうか。
調べるのは N-1 まででなく，N//2 まで調べればいい。
2 と 3 以上の奇数で割り切れるかだけ調べればいい。
これで計算量はおよそ半分になるのだが，計算量をオーダー記法で表すとのままである。しかし次のプログラムなら計算量はになる。というのも i * i <= N というのは i が 以下ということだからだ。
O(N )O(√N )

O(N )√N

素数：例 2def f(N):if N == 1:
return 0
i = 2
while i * i <=N:
if N % i == 0:
return 0i += 1
return 1

6実は 2002 年にインド工科大学の研究者から出された『PRIMES is in P』という論文で，素数判定は の多項式のオーダーでできることが証明されている。 やは の指数関数のオーダーであるから，これは非常に画期的な結果であった。もっとも，これで素数判定が速くなったということはないのだが（多項式の次数や係数が大きすぎるため）。
ところで，ここまでにあげたアルゴリズムは素因数を見つけることで素数判定をしているから，実質的には素因数分解に近いことをしていると考えられる。実は整数の性質を用いることで，具体的な素因数を見つけなくても素数かどうかを判定することができる。
たとえばフェルマーの小定理 「 が素数ならば，の範囲のすべての整数 に対して」 の対偶 「の範囲のある整数 に対してであれば， は素数でない」 を用いて「の範囲のすべての整数 に対してならば は素数（だろう）」 とする判定方法を「フェルマーテスト」という。これは非常に簡便な方法ではあるのだが，合成数であってもこのテストを通ってしまう数（カーマイケル数）があるので，フェルマーテストで素数と判定されても確実に が素数だとは言えない（そもそもフェルマーの小定理の逆だから，成り立つ保証がない。ちなみに合成数と判断されたものは確実に合成数）。
このように，合成数の判定は正しいが素数の判定が保証できない判定方法を「確率的素数判定」という（Miller-Rabin 法なども有名）。ある程度の誤判定はあるのだが，実用的には差し支えないと考えて使うこともある。一方，確実に素数の判定ができるものを「決定的素数判定」というが，大抵は計算量が大きい。
3 学期の情報の授業で「RSA 暗号」について学習するが，これは素因数分解の計算量が大きいことを利用した暗号である。他にも離散対数や楕円曲線（といっても楕円ではない）が用いられる暗号もあるが，これらに共通するのは「一方向性」すなわち 「 から を求めることは簡単であるが， からを求めることは極めて困難である」 ことである。このあたりは「問題」や「リーマン予想」と関係する極めて数学的な話であるが，量子コンピュータでどうこうできる話かもしれない。
log N

O(N )

O(√N )

log Npaap−1

ap−1a2 ≦ a ≦ p − 1≡ 1 (modp)≢ 1 (modp)

2 ≦ a ≦ p − 12 ≦ a ≦ p − 1pap−1a≡ 1 (modp)

ppx

f (x)

f (x)

P ≠ NP7x3.2 数当てゲーム

1 から N までの整数をランダムに発生させ，少ない質問回数（ただし質問はYes/No で答えられるもの）でそれを当てるゲームを考える。作戦として次の3 つを考えてみたが，どれが効率がいいだろうか。
1. 当てずっぽうに数を言って，偶然当たったら終了。
2. 1 から順に数を言って，当たったら終了。
3. a = 1，b = N とし，次の操作を繰り返す（当たりを x とする）：(a) a == b ならこれが当たりだから終了。
(b) c = (a + b) // 2 とする。x <= c なら b = c，そうでなければ a = c + 1 とする。
偶然の要素を均すために，100 回繰り返すプログラムにしたのが下の例である（random.randint(1, N)は 1 以上 N 以下の整数の乱数を生成する関数）。
def f(N):count = 0
for i in range(100):x = random.randint(1, N)
count += 1
while x != random.randint(1, N):count += 1
return count

数当てゲーム：例 1

def f(N):count = 0
for i in range(100):x = random.randint(1, N)

数当てゲーム：例 2a = 1
count += 1
while a != x:
a += 1count += 1
return count8

数当てゲーム：例 3

def f(N):count = 0
for i in range(100):x = random.randint(1, N)
a = 1
b = N
while a != b:c = (a + b) // 2
count += 1
if x <= c:b = celse:
a = c + 1
return count前にやったのと同じように N の値によって実行時間がどう変化するかを表にまとめなさい。
N
例1
例2
例3
100
1000
10000100000
例 1，例 2 はともに であるが，例 2 の方が速い（例 1 は同じ数を何度もたずねてしまう可能性がある）。一方，例 3 はそれよりずっと実行時間が小さいはずだ。このことについて考察してみよう。
例 3 の考え方は，a<=x<=b を保ちながら a と b の間隔を半分にしていこうということだ。つまり 回で当たりに行き着いたとしたら，半分にするのを 回することで候補を 1 個に絞れるということだから，およそとなる。このときなので，例 3 の計算量はである。このような探し方を二分探索という。順番通りに探していく線形探索に比べればずっと速いのだが，あらかじめデータを大小順に並べておく必要があるので，そのための計算量が必要になることもある。
O(N )kk2

k = log2NO(log N )9k= N

3.3 フィボナッチ数列というように，前 2 つの項を足した値が次の項になるような数列をフィボナッチ数列という。ここでは関数を使ってこれを実現してみる。
1, 1, 2, 3, 5, 8, 13, ⋯f (0) = f (1) = 1のとき
具体的なプログラムは上の定義をそのまま書くことで実現できる。このように関数の内部で自分自身を呼び出すことを再帰という。たとえば であれ
ば，その をに，$f(2)を f(1)+f(0)に…という風に遡って計算していく。
n ≧ 2f (n) = f (n − 1) + f (n − 2)f (4)f (3) + f (2)f (3)4(2) + f (1)

フィボナッチ数列：例 1

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

これも実行時間を計測して表にまとめてみよう。ただし例 1 は 40 まででやめておいた方がいい。後述するが，それ以上はあまりにも時間がかかりすぎる。実際，筆者の PC では f(50)が 30 分くらい，f(100)に至っては 100 万年以上かかる計算になる（かなり大雑把な計算ではあるが）。
N
例1
例2
例3
1020304050×100×1000 ×10たったの 40 でどうしてこんなに時間がかかってしまうのだろう。それを考えるために，例としての計算を分解してみる。
1.
2. 上の式でであるから
f (5) = 8f (5) = f (4) + f (3)f (4) = f (3) + f (2), f (3) = f (2) + f (1)f (5) = f (3) + f (2) + f (2) + f (1)3. さらにであるから

f (2) = f (1) + f (0)f (5) = f (2) + f (1) + f (1) + f (0) + f (1) + f (0) + f (1)4.
4 回の作業で終わったように見えるが，1.では 1 箇所，2.では 2 箇所，3.では3 箇所，4.では 1 箇所の計算をしているので，全部で 7 回の変換をしている。具
体的は値がわかっているのはとだけなのだから，式全体がと だけに分解されるまで変換がなされているわけで，この例ではが 8 個の ， に変換されるということは回の変換をしているのだ。
だから，これを求めるには回の計算が必要，ましてであるから…。
ではフィボナッチ数列の計算を簡単にやる方法はないのだろうか。そこで 2つの方法を紹介しておく（どちらも Python 特有の機能を使っている）。
f (5) = f (1) + f (0) + f (1) + f (1) + f (0) + f (1) + f (0) + f (1)f (0) = 1

f (1)
f (5)

f (1) = 1

f (0)

f (0)

f (1)

f (5) − 1 = 7

f (40) = 165580141

165580140

f (50) = 12586269025

def f(N):if N < 2:
return 1else:
a = b = 1
for i in range(N - 1):
a, b = a + b, a
return a

フィボナッチ数列：例 2

def f(N):if N not in f.memo:
f.memo[N] = f(N - 1) + f(N - 2)
return f.memo[N]f.memo = {0:1, 1:1}

フィボナッチ数列：例 311

例 2 は最初に書いたの項をループで求めている。
は から番号を増やせばいいので，繰り返し回数はとなる。
例 3 は既に計算した値を覚えておくというものだ。Python の「辞書型」といわれるデータ型の f.memo に f.memo[0] = 1，f.memo[1] = 1 をメモしておいて，N が f.memo になかったら，値を計算して f.memo[N]にメモを追加している。
計算量は例 2，例 3 ともに ではあるが，例 3 については既に計算した値を呼び出すときには である（と書いてある記事がネットには多いのだが，キーを探すためには に応じた計算量−よくある実装だとくらい−が必要ではないのかなあ）。ちなみに例 1 はおよそなので が 10 増えると計算量は約 120 倍になる。
1, 1, 2, 3, 5, 8, 13, ⋯f (1)f (N )

N − 1

N − 1

O(N )

O(1)
N

O(log N )O(1.62N)

N

第 4 章 おわりにコンピュータの性能が低かった時代は，少しでも（時間・空間ともに）計算量を減らそうと工夫をした。データの使いまわしはもちろん，プログラムの自己書き換えさえもよく使われる手段の一つであった。そこまでいかなくても，たとえば本校の成績処理システムでも時間がかかる集計の結果は別途保管しておいて，何度も計算しないで済むようにしていた。
しかし今は僅かな計算量の節約よりも，開発・運用の簡便さが求められている。先の成績処理システムの例も，当時は得点修正のたびに集計作業が必要で，それを忘れると不整合が生じたのだが，ある時期から集計は必要になるたびにその場で行うように変更した。コンピュータの速度改善がそれを可能にしたのだ。こういったやり方は「富豪的プログラミング」と揶揄されたりもしたが，逆にいえばそれができるようにコンピュータは進化してきた。とはいえ，細かい改良が必要な世界は歴としてあるのだし，そこまでいかなくてもフィボナッチ数列を 100 項求める程度のことで困難が起きるようでは話にならない。もっと効率のいい処理方法を求めることは常に求められることである。そしてそれはコンピュータに関するものだけではないだろう。我々の生活や仕事についても，社会や…おや，誰かが来たようだ。

12