お疲れさまです、みやもとです。
先月は記事を書くのにちょうどいいネタとか時間とかが用意できず、連続投稿が途切れてしまってちょっと残念です。
先日デブサミ関西に参加した折、書籍ブースの誘惑にあらがえずちょっとだけ本を買いました。
そのうちの1冊が「アルゴリズム図鑑 絵で見てわかる26のアルゴリズム」（翔泳社）。
以下、文中では「アルゴリズム図鑑」と表記します。
一応社会人1年目で入った会社の新人研修時にざっくり習ってはいたのですが、最近アルゴリズムとかアーキテクチャとか基本のところでもうちょっと勉強しないとな……と殊勝な気持ちになることがあって改めて勉強し直そうと購入。
少しずつ読み進めるつもりではありました。
図を多用してわかりやすく解説してくれていることもあり、アルゴリズム自体は理解できるというか「ああこんなのだったわ」と思い出しながら進められています。
ただ、ほぼ毎項まとめ部分で出てくるとある要素が、すらすらと読み進めることを阻むのです。
それは何か？答えは数式です。
数式を入れる都合上、本やWebからの引用箇所が引用の書式になっていないところがあります。
前後に引用の旨明記していますが、もし引用内に数式を入れる方法をご存じでしたらそっと教えていただけると幸いです。
数学を捨てた過去が理解を阻む
みやもとはド文系です。
中学時点で既に数学は赤点すれすれ、高校に入ると追試と補習の常連になり二年生になったタイミングで数学の授業が無いクラスに進みました。
それでよくエンジニアになろうと思ったものだと思われそうですが、基本情報技術者試験に出てくる計算式がぎりぎり理解の上限に収まっていたためどうにかなるかなと思った次第です。
そんな経歴ゆえか数学への苦手意識は深く、未だ数式が出てくる書籍はちょっと及び腰で眺めています。
そんな私の目の前に現れたのがこの数式です。
以下、「アルゴリズム図鑑」序章 「0-2 計算時間の測り方」より引用します。
\begin{multline}
(n × T_c + T_s) + ((n - 1) × T_c + T_s) + ((n - 2) × T_c + T_s) + … + ( 2 × T_c + T_s) + (1 × T_c + T_s) \\
=\frac{1}{2}T_cn(n + 1) + T_sn = \frac{1}{2}T_cn^2 + (\frac{1}{2}T_c + T_s)n
\end{multline}
正直この時点で反射的に本を閉じかけました。
何度か読み返してなお最後の式の収束具合はいまいちわからなかったものの、2番目との間に以下のように式をはさむことでなんとか理解。たぶん合ってるはず。
\frac{1}{2}T_cn(n + 1) + T_sn = \frac{1}{2}T_cn^2 + \frac{1}{2}T_cn + T_sn = \frac{1}{2}T_cn^2 + (\frac{1}{2}T_c + T_s)n
選択ソートの処理時間の考え方としてなんとかイメージが追いつきました。
また、読み進めていくと最も大きな影響を与える部分以外は削除して表現するという記載もあり、ひとまずその簡略化した数式で理解できればどうにかなりそうかなと思うことにしました。
そんな矢先に追撃です。
これも、「アルゴリズム図鑑」序章 「0-2 計算時間の測り方」から引用。
3n \log n + 2T_yn である場合は O(n \log n) と表現します。
logて何やねん
なんとなく見覚えはあるけど何だったかわからん……挫折再び。
とりあえず「そういうもの」と流して一旦読み進めようとしたのですが、1章終盤のヒープあたりから毎回処理時間の数式として「log」が出現。
2章のソートアルゴリズムでは後半ほぼほぼ出ずっぱりとわかったところで無視することを諦め、遅まきながらlogと向き合う覚悟を固めます。
大げさと思われましょうがそのぐらい数学への苦手意識は根深いのです。思い出される夏休み補習の悲しみよ。
検索してみる
まずは自分で調べてみようということで、素直に検索することにしました。
「log 数学」で検索して、検索結果で一番上に出てきたサイトへ。
しかし開いたとたんにでかでかと広告表示されてやる気がそがれたので、結局検索結果の脇に表示されたWikipediaを読むことに。
……頭が理解を拒否している気がしてきました。
対数（たいすう、英: logarithm）とは、ある数 x を数 b の冪乗 bp として表した場合の冪指数 p である。この p は「底を b とする x の対数（英: logarithm of x to base b; base b logarithm of x）」と呼ばれ、通常は logb x と書き表される。
Wikipedia冒頭の時点で、logが対数を表していることとべき乗と関係があることしかわからない。
AIの力を借りる
もう少しやわらかめの説明を求めて、AIに聞いてみることにしました。
Geminiに質問を投げたところ、以下のような回答が。
……うすうす予想はしていましたが、めちゃくちゃ子供に言い聞かせる文体になりましたね。
割と屈辱的です。屈辱と感じる資格があるかどうかはともかく。
この下に一応アルゴリズムの処理時間計算に関する記述もあったのですが、ちょっと質問が悪かったのでいまひとつ的を得ない内容だったため省略。
検索ふたたび
とりあえずlogが対数を表すことはわかったので、今度は「対数 公式」で検索。
以下のサイトでようやくlogの使用例にたどり着きました。
以下は上記サイトより引用
\begin{multline}
例えば、指数計算 3^2 = 9 を対数で表記すると、2 = \log_3 9 となります。\\
このとき、\log_3 9 は『3 を底とする 9 の対数』といいます。
\end{multline}
ここまできてようやく理解が追いついてきました。
本に出てきた数式を改めて考える
logについて理解が追いついてきたところで、本の記述に戻ります。
以下、「アルゴリズム図鑑 2-5 ヒープソート」の解説部分から引用。
\begin{multline}
ヒープソートの最初に、n個の数字をヒープに格納するための時間は、O(n \log n) \\
になります。これは、空の状態から1つずつデータを追加していけばよいのですが、\\
ヒープの高さは \log_2 n 以下であるため、1個の追加が O(\log n)で行えるからです。
\end{multline}
なんか途中で底の数字が表記から消えた……1
ともあれ、ヒープは最初の値を基準にして大きい・小さいの2方向に順番に値を振り分けて行くので底の値は2。
1段ごとに倍々になって最終的にnになるので、例えば全体で10個のデータをヒープに
振り分ける場合は
\log_2 10 = 3.3219280948874
ということですね。
ですよね？
（計算はこちらのサイトのお世話になりました）
数学はできた方がいい
今まで業務で数学できなくて困ったことはさほどないので気にしていなかったのですが、改めて理論とか勉強しようと思うとやっぱり数学できた方がいいな……としみじみしてしまいました。
また読み進めながらわからないことが出てきたら、己の無知をかみしめながら調べて記事にしていこうかと思います。
-
Geminiに聞いたところ、「計算量のオーダーでは、対数の底は通常、明記されません。これは、異なる底の対数は定数倍の違いしか生じないため、入力サイズが十分に大きくなると、その定数倍の違いは無視できるほど小さくなるからです。」と返ってきました。 ↩