第九の巻 計算量を体感せよ

師範 / 目安 35分

カメ師範が、九本目の巻物を広げました。ここからが師範の段です。

「知識で知るのと、待たされて知るのは違う。同じ答えを出す二つのやり方で、商店街の売上に重複があるかを調べよ。一つは総当たり。もう一つは、先に並べ替えてから隣だけを見る。そして、それぞれが何回比べたかを数えて持ってこい」

なぜ時間ではなく回数なのか。師範はこう言いました。「時は測るたびに違う顔をする。機械の機嫌にも左右される。比べた回数は嘘をつかん。同じ入力なら、いつ数えても同じ数じゃ。ゆえにこれは、腕を測る物差しになる」

総当たりは、すべての二つ組を一度ずつ比べます。100件なら4950回。件数を2倍にすると、回数はおよそ4倍に膨れます。これが O(n の2乗) の重さです。

並べ替えてから隣を見るやり方は違います。同じ値は並べ替えれば必ず隣り合うので、隣だけを見れば足ります。件数から1を引いた回数で済みます。並べ替え自体の手間を足しても、総当たりの膨らみ方には遠く及びません。

2000件でこの2つを走らせたとき、数がどれだけ離れるか。それを自分の目で見てください。

完成条件

countCompares という関数を1つ定義してください。どの言語で解いても関数名は countCompares にしてください。Python でも snake_case ではなく、この綴りのまま使います。

引数は1つ、調べる件数 n です。

まず、売上データをその場で作ります。i 番目の売上は (i * 37) % 1000 です。i は 0 から n - 1 まで動きます。どの言語で書いても同じ並びになる決め方なので、この式のとおりに作ってください。

そのうえで、次の2つを実装してそれぞれの比較回数を数えます。

1. 二重ループ — 添字 i と、それより後ろの添字 j のすべての組み合わせについて、値が等しいかを1回比べます。比べるたびに回数を1つ増やします
2. 整列後の隣接比較 — 売上を昇順に並べ替えたあと、隣り合う2つが等しいかを先頭から順に比べます。ここも比べるたびに回数を1つ増やします

並べ替えそのものは、各言語の標準の並べ替えを使って構いません。数えるのは、重複を探すための比較だけです。並べ替えの内部で起きる比較は数えません。

返すのは次の形をした1つの文字列です。

n が 0 や 1 のときは、どちらの比較も起きません。回数はどちらも 0 になります。件数から1を引いた値をそのまま使うと、n が 0 のときに負の数になります。そこだけ気をつけてください。

進め方

白紙から書いてください。手が止まったらヒントを開けます。ヒントは3段階で、①方針、②使う構文、③部分解の順に出ます。1つも開けずに通せたら、その問題は自分のものです。

開かずに10分粘って進まないなら、①だけ開けてください。粘る時間そのものには価値がありません。価値があるのは、自分で書いた行が動いた瞬間です。

通ったら、n に 100、200、400 を入れて二重ループの回数がどう伸びるかを見てください。件数が2倍になるたび、回数はおよそ4倍です。一方の整列後は、素直に2倍にしかなりません。この差の記憶が、これからのあなたの設計を変えます。

1. 関数名は4言語すべてで countCompares にすること(Python も snake_case にしない)
2. 引数は調べる件数 n の1つ
3. 売上データは i 番目が (i * 37) % 1000 となるように、i を 0 から n-1 まで動かして作ること
4. 二重ループは、添字 i とそれより後ろの添字 j のすべての組み合わせを1回ずつ比べ、そのたびに回数を1つ増やすこと
5. 整列後は昇順に並べ替えたあと、隣り合う2つを先頭から順に比べ、そのたびに回数を1つ増やすこと
6. 並べ替えは各言語の標準の並べ替えを使ってよいが、その内部で起きる比較は数えないこと
7. 戻り値は「二重ループ ○回 / 整列後 ○回」の形をした1つの文字列であること
8. n が 0 や 1 のときはどちらの回数も 0 にすること(負の数にしない)