Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

「この並べ方は速い」と言うとき、何と比べているのかがずれていることがある。本稿は、下界がどこから来るのかを数える。新しい定理も法則も主張しない。

第一に、下界は答えの通り数の対数である。$n=8$ では $\log_2 8!=15.2992$、切り上げて $16$ 回である（第2節）。

第二に、実際の手順はそれに近づく。二分挿入とマージは $n=8$ でどちらも最悪 $17$ 回、下界との差は $1$ 回しかない（第2節）。

第三に、手順によっては遠い。挿入ソートは最悪 $28$ 回で、下界の $1.75$ 倍である（第2節）。

第四に、平均も下界を割らない。二分挿入の平均は $\mathbf{15.5905}$ 回で、$\log_2 8!=15.2992$ を上回る（第2節）。

第五に、これが本稿の芯である。ある入力なら下界を割れる。すでに並んだ $8$ 個を挿入ソートに入れると $7$ 回で済み、下界 $16$ を大きく下回る（第3節）。

第六に、分離子は、ある入力での回数を問うか、どの入力でも足りる回数を問うかである。下界が守っているのは後者だけである（第4節）。

キーワード：比較ソート、下界、決定木、最悪と平均、全数え上げ、模型。

射程（何を示さないか）

新しい定理も法則も主張しない。比較による整列の下界が $\log_2 n!$ であること（決定木の葉が $n!$ 個要ること）、マージソートと二分挿入ソートがその桁に収まること、平均についても同じ下界が立つことは、いずれも既知である。実装の速さを論じない。記憶の読み書き、定数倍、並列化は主題ではない。数えるのは比べた回数だけである。最適な回数を主張しない。各 $n$ で必要な最小の比較回数そのものは本稿が求めたものではない。数えたのは三つの手順の実測である。比較しない整列を扱わない。計数ソートや基数ソートのように、値そのものを使う方法には入らない。大きさを一般化しない。$n=9$ 以上は数えていない。既刊との関係：論文759 は、同じ回数だけ比べても遅い記憶を読む回数は木の分岐で決まることを示した。本稿はその隣に置く。あちらは比べた回数が同じでも費用が違うことを示し、こちらは比べた回数そのものの底を数える。論文300 は同根か別根かが判定できることを示した。ある入力での回数と、どの入力でも足りる回数は、その基準で別根である。加えたのは、三つの手順を $n=4$ から $8$ まで全順列で流して最悪と平均を並べたこと、下界との差が $n=8$ で $1$ 回しかないと測ったこと、並んだ入力なら $7$ 回で済むことを測って下界の向きを言い直したこと、分離子を「ある入力か、どの入力でもか」に置いたことである。

1. 記法と問い

設定：$n$ 個のものを、二つずつ比べることだけで小さい順に並べる。比べた回数だけを数える。

$$\text{答えの通り数}=n!,\qquad
\text{比べる回数の下界}=\lceil \log_2 n! \rceil$$

一回の比べは答えを高々半分に絞るので、$n!$ 通りを一つに絞るにはこれだけ要る。右辺には入力の中身が一切入っていない。

問い：この下界は、何についての下界なのか。

2. 下界と、実際の回数

計算 2.1：$n=4$ から $8$ まで、全順列を三つの手順に流して比べた回数を数えた。

観察 2.2　どの手順も下界を割らなかった。最悪の回数は五つの大きさすべてで切り上げた下界以上である。一回の比べが答えを半分にしか絞れない以上、これは避けられない。

観察 2.3　近い手順と、遠い手順がある。$n=8$ で二分挿入とマージは $17$ 回、下界 $16$ との差は $1$ 回しかないのに、挿入ソートは $28$ 回で $1.75$ 倍である。同じ下界の下で、手順の良し悪しがそのまま出る。

計算 2.4：平均も数えた。

観察 2.5　平均も下界を割らない。$n=8$ の二分挿入の平均は $15.5905$ で、$15.2992$ を上回る。答えを絞る量は平均でも同じだけ要るからである。

3. ある入力なら、下界を割れる

計算 3.1：すでに小さい順に並んだものを挿入ソートに入れた。

観察 3.2　これが本稿の芯である。下界を割った。$8$ 個で $7$ 回、下界 $16$ の半分以下である。矛盾ではない。下界は「どの入力でも足りる回数」についての話で、ある入力での回数についてではないからである。

観察 3.3　同じ手順が、最悪 $28$ 回で最良 $7$ 回である。$4$ 倍の開きがある。「速い」と言うときは、どの入力についてかを付けなければ意味が決まらない。

観察 3.4　下界は入力を見ていない。$\lceil\log_2 n!\rceil$ に入るのは $n$ だけで、値も並び方も入らない。だから「こういう入力なら速い」は、この式に何の影響も与えない。

4. 分離子

観察 4.1　分離子は、ある入力での回数を問うか、どの入力でも足りる回数を問うかである。前者はいくらでも小さくできるが、後者は $\log_2 n!$ より下げられない。二つは同じ「回数」という語で呼ばれるが、別の量である。

観察 4.2　論文759 の隣に置く。759 は、同じ回数だけ比べても遅い記憶を読む回数は木の分岐で決まることを示した。あちらは比べた回数が同じでも費用が違うことを数え、こちらは比べた回数そのものの底を数える。上と下の両側から同じ量を挟んでいる。論文300 は同根か別根かが判定できることを示した。ある入力での回数と、どの入力でも足りる回数は、その基準で別根である。

観察 4.3　言わないこと。実装の速さも、各 $n$ で必要な最小の回数も、比較しない整列も扱わない。示したのは、下界が入力ではなく答えの通り数から来るということである。

5. 点呼と結び

1. 下界は $\log_2 n!$（第1節）：入力が入らない。
2. $n=8$ で $15.2992$（計算 2.1）：切り上げて $16$。
3. 二分挿入とマージは最悪 $17$（計算 2.1）：差は $1$ 回。
4. 挿入は最悪 $28$（計算 2.1）：下界の $1.75$ 倍。
5. 二分挿入の平均は $\mathbf{15.5905}$（計算 2.4）：平均も割らない。
6. 並んだ $8$ 個なら $7$ 回（計算 3.1）：本稿の芯。
7. 下界 $16$ の半分以下（計算 3.1）：矛盾ではない。
8. 同じ手順で $28$ 回と $7$ 回（観察 3.3）：$4$ 倍の開き。
9. 式に入るのは $n$ だけ（観察 3.4）：値も並びも入らない。
10. ある入力か、どの入力でもか（観察 4.1）：分離子・論文759・300。

結び：比べる回数の下界は、入力ではなく答えの通り数で決まる。$n=8$ の下界は $\log_2 8!=15.2992$、切り上げて $16$ 回で、二分挿入とマージはどちらも最悪 $17$ 回とそこに $1$ 回まで近づき、挿入ソートは $28$ 回とその $1.75$ 倍かかる。一回の比べが答えを高々半分にしか絞れないからである。ところがすでに並んだ $8$ 個を挿入ソートに入れると $7$ 回で済み、下界 $16$ の半分以下になる。下界は「どの入力でも足りる回数」についての話で、ある入力での回数についてではないからである。同じ手順が最悪 $28$ 回・最良 $7$ 回と $4$ 倍も開くので、「速い」と言うときはどの入力についてかを付けなければ意味が決まらない。既刊との位置：論文759 が「同じ回数でも費用が違う」を数えた隣に、回数そのものの底を数えて置き、論文300 の規律で二つの「回数」を別根として扱った。正直に言えば、数えたのは $n=8$ までの三つの手順で、各 $n$ で必要な最小の回数そのものは求めていない。

参考文献

1. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley.
2. 山岸勇輝 (2026). 『三百本目の点呼、同根か別根かは、判定できる』[論文300]. YOI: https://www.yamagishiyuuki.com/yoi/300 ・ DOI: 10.5281/zenodo.22171914
3. 山岸勇輝 (2026). 『同じ回数だけ比べても、遅い記憶を読む回数は木の分岐で決まる』[論文759]. YOI: https://www.yamagishiyuuki.com/yoi/759 ・ DOI: 10.5281/zenodo.23015187

作成にあたって：本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI（大規模言語モデル）の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝（2026）「比べる回数の下界は、入力ではなく答えの通り数で決まる」［論文843］. YOI: https://www.yamagishiyuuki.com/yoi/843

@misc{yamagishi2026yoi843,
  author = {Yamagishi, Yuuki},
  title = {The Lower Bound on Comparisons Comes From the Number of Answers, Not From the Input},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/843},
  note = {Preprint, edition 1}
}