単純ソートは遅い？
これまでの記事で、私たちは「挿入ソート」「選択ソート」「バブルソート」という3つの基本的なソートアルゴリズムを学んできました。
11 記事
ソートアルゴリズム
ソートアルゴリズムについて、単純ソート、分割統治法などの比較するソート、基数ソートなどの比較しないソートまでその仕組みを...
これらはアルゴリズムの動きが直感的で、プログラミング学習の第一歩として最適です。
しかし、これらのソートは「単純ソート」と呼ばれており、共通する大きな弱点があります。それは、「データの数が増えれば増えるほど、急激に処理時間が遅くなる」ことです。
この記事では、その「遅さ」を測るための重要なモノサシである「計算量（けいさんりょう）」と、それを表す「O（オーダー）記法」について、中学生でもわかるように解説していきます。
(疑似的に処理毎に待機時間0.02秒を持たせてシミュレーションし、理論値は二次関数での近似)
図1 選択ソートのデータ数と処理時間の関係
そもそも「計算量」ってなに？
難しく考える必要はありません。「計算量」とは、一言でいえば「その作業の面倒くささ度」のことです。
もっと具体的に言うと、「データの数（n）が増えたときに、処理の手間（ステップ数）がどれくらいの勢いで増えるか」を示す指標です。
ソートアルゴリズムでは、比較の回数や交換の回数がこの処理の手間に当たります。
O（オーダー）記法の考え方
この「手間の増え方の勢い」を、世界共通のシンプルな記号で表すルールが「O（オーダー）記法」です。(この”O”をランダウの記号と言います。)
オーダーのルール(超簡単に言うと?)
O記法には2つの重要なルールがあります。
- 「一番勢いが強いヤツ」だけを残す
- 定数（係数）は無視する
どういうことでしょうか？
例えば、あるアルゴリズムの手間を計算したら、 3n2 + 5n + 100 回だったとします。
n=10（データ10件）の時は、
( 3 × 100 ) + ( 5 × 10 ) + 100 = 300 + 50 + 100 = 450回 です。
図２ Nが小さいと定数もそれなりに計算回数に影響する
この時点では、 3n2 も 5n も 100 も、それなりに影響力があります。
では、n=1,000,000（データ100万件）の時はどうでしょう？
- 3n2 = 3,000,000,000,000（3兆）
- 5n = 5,000,000（500万）
- 100 = 100
3兆回の手間に比べたら、 500万回や 100回なんて、ほぼ誤差ですよね。
図３ 階乗の影響力が強い
データ数 n が大きくなればなるほど、 n2 （二乗）の項の影響力が圧倒的になります。
O記法は、この「一番影響力が強い項（＝一番勢いが強いヤツ）」だけに着目します。
だから、3n2 + 5n + 100 の本質的な勢いは「 n2」だ、と考えます。
さらに、 3n2 の「 3」のような定数（係数）も無視します。なぜなら、「 3n2 」も「 5n2」も「 10n2 」も、グラフにすれば形は違えど「二乗の勢いで増えていく」という本質は同じだからです。
結果、3n2 + 5n + 100 の計算量は O[n2] （オーダー・エヌ二乗）と表記します。
ちょっと練習問題
Q1. (計算回数) = n + 1 のオーダーは？
Q2. (計算回数) = 4n3 + n + 300 のオーダーは？
Q3. [発展] (計算回数) = n log(n) + n + 1 のオーダーは？
(解答と解説はこの記事の最後の方にあります)
グラフで見る「勢い」の違い
このO記法で表される「勢い」をグラフで見ると、その違いは一目瞭然です。
- O[1] (青): データが増えても手間が変わらない（最強）。
- O[log n] (緑): データが倍になっても手間が少ししか増えない（非常に速い）。
- O[n] (黄): データ量と手間が比例する（速い）。
- O[n log n] (紫): O[n]より少し遅いが、 O[n2]より圧倒的に速い。
- O[n2] (赤): データが増えると急激に手間が増える。
図４ オーダーごとの手間の増える勢い
単純ソートの計算量を考えてみよう
では、過去の記事で紹介した選択ソートやバブルソートの計算量はどうなるでしょうか？
選択ソート（最大値選択法）の計算量
- データが n 個ある。
- まず「最大値」を見つけるために、全データに対し（ n-1 回）比較する。
- 最大値が1個確定し、残りは n-1 個になる。
- 次に、 n-1 個の中から最大値を見つけるために（ n-2 回）比較する。
- これを繰り返していくと、比較回数の合計は…( n-1 ) + ( n-2 ) + ( n-3 ) + … + 1 回
これは数学で習う「1から n-1 までの合計」等差数列なので、 式１のようになります。
O記法のルールを適用してみましょう。
式１の中で一番勢いが強いのは「 n2 」の項ですね。
定数係数や、勢いの弱い -n は無視します。
したがって、選択ソートの計算量は O[n2] となります。
選択ソートの復習はこちら
選択ソートの仕組みを徹底解説！アニメーションで学ぶ「一番を探す」ソート【ソートアルゴリズム入門】#1
「選択ソート（最大値選択法）」の仕組みとは？「未ソート領域から最大値を選び、末尾に配置する」という直感的な動きを、インタラクティブなツールで体感。0.2秒ごとに最大値を自動探索するアニメーションで、探索→交換のステップを分かりやすく解説します。
挿入ソートの計算量
最も計算に手間がかかる場合(最悪計算量)を考えると、挿入ソートの場合、昇順に並び替えたいのに元のデータが降順だった時やその逆の場合になります。
- データが n 個ある。
- まず一つ値を選びそれより小さいものを、見つけるまで最悪の場合全データに対し（ n-1 回）比較し、入れ替わる。
- 自分より小さいものが見つかったらそこで挿入をやめる、未ソート部分は n-1 個になる。
- 次に、 n-1 個の中から一つ選びそれより小さいものを、見つけるまで（ n-2 回）比較する。
- これを繰り返していくと、比較回数の合計は…( n-1 ) + ( n-2 ) + ( n-3 ) + … + 1 回
選択ソートと同じになったので、同様にオーダーの考え方から、挿入ソートの計算量は O[n2] となります。
挿入ソートの復習はこちら
挿入ソートの仕組みを徹底解説！アニメーションで学ぶ「正しい位置に差し込む」ソート・単純挿入法【ソートアルゴリズム入門】#2
ソートアルゴリズム入門「挿入ソート」の仕組みを解説。トランプの手札を並べ替えるような直感的な動きを、インタラクティブなアニメーションツールで1ステップずつ確認できます。「整列済みの場所に差し込む」とはどういうことか、その目で見ながら学びましょう。
バブルソートの計算量
最も計算に手間がかかる場合(最悪計算量)を考えると、バブルソートも挿入ソートと同じで、昇順に並び替えたいのに元のデータが降順だった時やその逆の場合になります。
- データが n 個ある。
- 一つ値を選びそれより小さいものがあったら入れ替える、全データに対し（ n-1 回）比較し、入れ替わる。
- 2.の手順で最大値が一番右に来て、未ソート部分は n-1 個になる。
- 次に、 n-1 個に対して2.と同じ処理を行い（ n-2 回）比較する。
- これを繰り返していくと、比較回数の合計は…( n-1 ) + ( n-2 ) + ( n-3 ) + … + 1 回
またしても、選択ソートや挿入ソートと同じになったので、同様にオーダーの考え方から、バブルソートの計算量は O[n2] となります。
バブルソートの復習はこちら
バブルソートの仕組みを徹底解説！アニメーションで学ぶ「ひたすら比較・交換」ソート・単純交換【ソートアルゴリズム入門】#3
ソート入門の定番「バブルソート」の仕組みを解説。隣同士を比較して交換するだけの単純な動きを、インタラクティブなツールで1ステップずつ追体験できます。重い（大きい）値が水底に沈んでいく（＝末尾に確定する）様子をアニメーションで学びましょう。
なぜ単純ソートは遅いのか？（最悪計算量)
先ほどの計算量の計算にも出てきましたが、アルゴリズムにとって一番運が悪いデータ（例：バブルソートで完全に逆順のデータ）が来た時の計算量を「最悪計算量」と呼びます。
単純ソートの最悪計算量は O[n2] です。
グラフで見る「勢い」の違いで見たように、O[n2] はデータ数が増えたときとてつもなく計算に時間がかかってしまいます。
図４(再掲) オーダーごとの手間の増える勢い
O[n2] がどれほど絶望的なのか、データ数 n と手間の関係を見てみましょう。
（仮に1回の処理に 0.000001秒 かかるコンピュータで計算すると…）
| データ数 n | O(n)（比例）の手間 | O(n2)（二乗）の手間 |
| 100件 | 100回 (0.0001秒) | 10,000回 (0.01秒) |
| 10,000件 | 1万回 (0.01秒) | 1億回 (約1.6分) |
| 100万件 | 100万回 (1秒) | 1兆回 (約11.5日) |
| 1億件 | 1億回 (約1.6分) | 1京回 (約317年) |
O[n] のアルゴリズムなら1億件でも数分で終わるのに、O[n2] の単純ソートでは100万件のデータですら11日もかかってしまいます。
これが、単純ソートは遅いといる理由です。
まとめ
- 計算量とは「データ数 n が増えたときの手間の増え方」を示すモノサシです。
- O記法は、計算量の「勢い」だけに着目した書き方（例： O[n], O[n2] ）です。
- 挿入・選択・バブルソートなどの「単純ソート」は、計算量が O[n2] です。
- O[n2] は、データ数が多くなると処理時間が爆発的に増える（グラフが急激に立ち上がる）ため、実用上、多くのデータを扱うのには向きません。
～次回予告～
O[n2]の遅さを理解したところで、次回からはこの弱点を克服した、より高速なソートアルゴリズムの世界へ進みます。
グラフのO[n2] と O[n] の間にあった、O[n log(n)]という効率的なアルゴリズム、「クイックソート」や「マージソート」はどのようにして速さを実現しているのか、これらのソートは”分割統治法”という考えに基づいています。次回の記事ではその仕組みを解説し、その後クイックソートやマージソートについて紹介していこうと思います。
分割統治法とは？高速なソートアルゴリズム【ソートアルゴリズム入門】#5
「分割統治法」とは？ 難しい問題を「小さく分けて、後で合体する」ことで高速に解くアルゴリズム戦略です。O(N^2)の壁を破るO(N log N)の鍵となる、マージソートやクイックソートの基本思想を図解します。
11 記事
ソートアルゴリズム
ソートアルゴリズムについて、単純ソート、分割統治法などの比較するソート、基数ソートなどの比較しないソートまでその仕組みを...
練習問題の解答と解説
ちょっと練習問題 – 解説 –
Q1. (計算回数) = n + 1 のオーダーは？
- 解答: O[n]
- 解説: n と 1 を比べます。データ数 n が100万になれば、n (100万) に比べて 1 は「誤差」のようなものです。一番勢いが強いのは $n$ です。したがって、オーダーは O[n] となります。これは「データ量と手間が比例する」アルゴリズムですね。
Q2. (計算回数) = 4n3 + n + 300 のオーダーは？
- 解答: O[n3]
- 解説:4n3 (nの3乗)、 n、 300 の3つを比べます。n が大きくなればなるほど、 n3 (n×n×n)の増え方の勢いが圧倒的になります。（n=100 の時点で n3 は100万ですが、 n は100です）したがって、一番勢いが強いのは n3 の項です。O記法のルールに従い、係数の 4 は無視するため、オーダーは $O(n^3)$ となります。（これは私たちが学んだ O[n2}よりも、さらに急激に遅くなるアルゴリズムです）
Q3. [発展] (計算回数) = n log(n) + n + 1 のオーダーは？
- 解答: O[n log(n) ]
- 解説: n log(n) 、 n 、 1 を比べます。n log(n) という見慣れない項が出てきましたねlog(n) は、 n が100万になっても「約20」にしかならないような、n よりも増え方が圧倒的に緩やかな項です。よってオーダーは、O[n log(n) ]となります。logがなぜ出てくるのかについては以下の記事で図と例を用いて説明しています。
なぜ計算量がn log(n)？”log”が出てくる訳をわかりやすく紹介【ソートアルゴリズム入門】#7
O[n^2] を超える高速なソート（クイックソート等）は O[n log n] と呼ばれます。なぜ突然log（対数）が出てくるのか？ その秘密は「半分に分ける」という最強の戦略「分割統治法」にありました。log の正体を視覚的に解き明かします。
ここまで読んでいただきありがとうございます。
では、次の記事で。 lumenHero
