YOI 702：分けても速くならない場合がある：決めているのは、分け方ではなく、まとめる仕事である

論文702 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/702 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。Zenodo でも公開しています（DOI：10.5281/zenodo.23014909）。

本文のサイトの記事は、これから順に公開します。

@misc{yamagishi2026yoi702,
  author = {Yamagishi, Yuuki},
  title = {Dividing Does Not Always Make It Faster: What Decides Is Not the Division but the Combining},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/702},
  doi = {10.5281/zenodo.23014909},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969440・969456・969461 に記録されました（2026年10月01日 19:28（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

分割統治は速くなる工夫だと説明される。だが分けたあとをまとめる仕事が重ければ、分割は何も得ていない。どちらが支配するかと、指数差が定数倍にいつ勝つかを数える。新しい定理も法則も主張しない。

第一に、これが本稿の芯である。分けても得られないことがある。$a=2$・$b=2$ で、まとめる仕事が $n$ なら $n\log n$ になるが、$n^2$ ならまとめる側が支配して $n^2$ のままである（第2節）。

第二に、支配するのは、二つの指数の大小だけである。分ける側の指数 $\log_b a$ とまとめる側の指数を比べ、大きいほうが答になる。等しければ対数が一つ付く（第2節）。

第三に、得られるときでも、得は小さい。シュトラッセンの指数 $\mathbf{2.807355}$ は素朴な $3.000000$ より小さいが、差は $\mathbf{0.192645}$ しかない（第3節）。

第四に、その差は、定数倍の不利になかなか勝てない。定数が $2$ 倍不利なだけで追いつくのは $n>\mathbf{36.527043}$、$5$ 倍なら $n>\mathbf{4248.919974}$、$20$ 倍なら $n>\mathbf{5669014.762747}$ からである（第3節）。

第五に、指数差が大きければ、話は変わる。カラツバは指数 $\mathbf{1.584963}$ で差が $\mathbf{0.415037}$ あるので、$2$ 倍の不利でも $n>\mathbf{5.312610}$ で追いつく（第3節）。

第六に、分離子は、分ける側とまとめる側のどちらが支配するかである。分け方の巧拙ではない。まとめる仕事の指数が大きければ、どう分けても同じである（第4節）。

キーワード：分割統治、マスター定理、計算量の指数、定数倍、交差点、漸近と実用

Abstract

Divide and conquer is explained as a way of going faster. But if the work of putting the pieces together is heavy, the division has gained nothing.Which side governs, and when an exponent gap beats a constant factor, are counted here.No new theorem or law is claimed.

First, and this is the core. Dividing sometimes gains nothing、with $a=2$ and $b=2$, combining work of $n$ gives $n\log n$, while combining work of $n^2$ leaves $n^2$ (Section 2).

Second, what governs is only which of two exponents is larger、compare $\log_b a$ with the exponent of the combining work; the larger is the answer, and only when they are equal does a logarithm appear (Section 2).

Third, even where there is a gain, it is small、Strassen’s exponent $\mathbf{2.807355}$ lies below the naive $3.000000$ by only $\mathbf{0.192645}$ (Section 3).

Fourth, that gap struggles against a constant factor、a factor of merely $2$ against it postpones the gain to $n>\mathbf{36.527043}$, a factor of $5$ to $n>\mathbf{4248.919974}$ and a factor of $20$ to $n>\mathbf{5669014.762747}$ (Section 3).

Fifth, a larger gap changes the story、Karatsuba’s exponent is $\mathbf{1.584963}$, a gap of $\mathbf{0.415037}$, so even a factor of $2$ is overtaken at $n>\mathbf{5.312610}$ (Section 3).

Sixth, the separator is which side governs、not how cleverly the problem is divided: if the combining exponent is larger, every division gives the same answer (Section 4).

Keywords: divide and conquer, master theorem, exponent of complexity, constant factor, crossing point, asymptotic against practical

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/702/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/702 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。

YOI の一覧へ