図解でスッキリ！Big O記法のやさしい入門
引用元：https://news.ycombinator.com/item?id=45002182
この記事とHNのコメントは、Big O記法の解説記事と、その技術的詳細をめぐるお決まりの論争パターンを踏襲してるね。Ned Batchelderの記事[0] https://nedbatchelder.com/text/bigo.htmlと[1] https://nedbatchelder.com/blog/201711/toxic_experts.htmlが参考になるよ。
最初の記事のコメント読んだら、Pyonってやつは超毒舌でうるさいけど、Nedの反論もイマイチだね。NedはPyonの批判の内容まで否定してるけど、なんでだろ？Nedはオンラインでの共感とコミュニケーションは正しいけど、教育者としてPyonの指摘がなんで過剰に技術的で難解なのか説明してほしかったな。NedはPyonの批判に真摯に向き合ってたのに、その後のブログ記事でその分析がないのは残念すぎる。
ブログってさ、著者は読者が前の記事も全部読んでるって思いがちだけど、実際は違うんだよね。何年も経ってから見ると、前後の文脈が分からなくて、何が言いたいのか全然理解できないことってあるよね。
あの分析がフォローアップ記事にないのはね、Pyonが正しいかどうかじゃなくて、奴が”嫌なやつ”だったからだよ。最初の言葉が”恥を知れ”でさ、その後もずっと嫌な態度だったんだ。いくら正論でも、嫌な言い方したらみんなに嫌われるってこと。
これらの記事の教訓は、間違った説明を直すのをやめるべきじゃなくて、一部のネットユーザーは著者を優しく助けるより、ネットバトルに勝ちたいだけってことだよ。Pyonのコメントは超攻撃的で、まさにネット荒らしって感じだった。だからって”技術的な詳細なんてどうでもいい、不正確でもOK”って誤解しちゃダメだからね。
この記事の著者がHNにコメントを求めて投稿したんだから、批判されるのは当然だよ。HNは素人向けじゃないし、専門家目線で正確さを厳しく評価される場所なんだから。著者が専門家じゃなかったせいで基本的な間違いがあったんだから、批判されるのは当たり前だし、むしろ妥当な反応だよね。
いい入門記事だね！Big Oは最初にCracking the Coding Interviewで学んだよ。ヨーロッパの大学って、基本的なプログラミングの授業でも計算量記法を教えないことが多いらしいんだ。この記事は、もっと分かりやすく説明してくれてて助かる！
数学をちゃんと読み書きできるのって、本当に大事だよね。このややこしい混乱も、たった一文の定義で全部解決できるんだから。
おいら、毒舌専門家だよ！ブログ記事で複雑なテーマを教えるの、本当に嫌いなんだ。たいてい非専門家が教えてて、不正確な情報がネット中に広まって、読者はブログ記事以上を学ぼうとしないから、さらに無知になる。それに、このページのレイアウトも気に入らないね。ADHDの俺には、情報がごちゃ混ぜの壁みたいに見えて、全然頭に入ってこないんだ。Simple Wikipediaのページ https://simple.wikipedia.org/wiki/Big_O_notation の方がずっとストレートでいい。Wikipediaの本格的なページは数学だらけで、こんなに複雑なものを簡単に説明しようとするのは多分間違いだ。
専門家ぶってるけど、ブログ記事で複雑なことを教えるのは不正確な情報を広めるから嫌だ。たいてい非専門家が教えてるし、読者はそこで学習を終えちゃう。専門家がもっと良いコンテンツを作るか、知識の囲い込みをやめるべきだね。実務ではBig Oの厳密な定義なんて誰も必要としてないよ。
「専門家がコンテンツを作らない」ってのは単純化しすぎだね。複雑すぎてブログ記事には収まらないこともあるんだ。それは知識の囲い込みじゃない。記事がBig Oでいくつか深刻な間違いを犯してたけど、著者が素直に認めたのは良かった。視覚的な表現は本当に素晴らしかったよ。
物事の要点を説明するのって、たとえ完全に正確じゃなくてもすごく価値があると思うよ。それができないケースは、実用的なコンピュータプログラミングではめったにないんじゃないかな。
「なぜ」って聞く前に、「そもそもそうなってる？」って考えてみて。複雑なトピックに関する良い記事だってあるんだ。ただ、質の低い記事に埋もれちゃってるだけだよ。
昔、車のブレーキ交換を教わったけど、大事な詳細が抜けてたせいで後で失敗した経験があるんだ。専門家が詳細なコンテンツを作れないのはわかるけど、不正確な情報が広まるのは止めたい。修正の仕方はもっと良くできるけど、訂正しないのはまずいと思うよ。
半専門家として思うのは、ブログで深い内容を書くのは難しいってこと。詳しく書こうとすると、短くまとめるのが大変なんだよね。Jeremy ColeのInnoDBシリーズは、読者が基礎を知ってる前提で書いててすごいと思う。自分はつい基礎から説明しちゃうけど。Linus TorvaldsのLinuxカーネルの話みたいに、ゲートキーピングも必要な場面があるんじゃないかな。記事はこちら→ https://blog.jcole.us/innodb/
理想は「丁寧」で「正確」な両方だけど、もし選ぶなら、冷たくても正確な医者を選ぶね。親切だけど間違った診断をする医者より、冷淡でも正しい治療をしてくれる医者の方がいいってことだ。
書くのって最高の勉強法だよね。非専門家だって書くことで学んでるかも。不正確な情報が全部広まるわけじゃないし、ブログ記事からもっと深く学ぼうとする人もいる。ブログが学びのきっかけになることもあるんだから、非専門家のための場所も必要だよ。懐疑的に読めばいいんだしね。
大抵の場合、間違った知識でも、全く知識がないよりはマシだよね。たぶん、どんな人でも自分が専門家じゃない分野では、不正確な知識を使ったり広めたりしてるんじゃないかな。
それはトピックと不正確さの度合いによるね。「ハッシュマップがO(1)で良い選択肢」ってのはそこまで間違ってない。でも「整数を文字列で保存すれば精度が保証されるから、decimalやfloatより好ましい」ってのは、前半は正しいけど結論は全然違うって例もあるんだよ。
みんなを満足させるのは無理だよね。俺の経験だと逆なんだ。カラフルで小箱だらけ、写真にキャプション、いろんなフォントサイズ、かわいいマスコットとか、読む順番すら分かりにくい本は嫌いなんだ。むしろ70～80年代以前の古い本、時には40年代の本から学ぶ方がずっと簡単だったよ。単一カラムで白黒だけど、著者の個性が光ってて全然退屈じゃない。確率論の本とか、読者を真剣に扱ってくれる章があってさ、ドライな定義を並べるんじゃなくて、歴史を通して意見のある筋道が通ってたんだ。そういう方が、情熱が隠されまくってるような、委員会が書いたみたいな怪物よりずっと好きだよ。言葉一つ一つをチェックしなきゃいけないような、半ページもある定義や厳密な定理の方が、漠然とした説明より信頼できる。今の本は形式的な定義を全然載せないから、何となく分かった気になってるけど、「結局これってどっちなの？」ってモヤモヤするんだ。それに、どこにでもある可愛い無関係な絵だらけの本が、結局のところADHDの人にとっても、集中を妨げない白黒の文章より本当に良いのか、俺は疑問に思うね。
新しく得た知識を定着させるための、素人が行う良い練習だけど、他の人にとっての有用性は低いかもね。
その内容を、もっと良い方法で再フォーマットできるんじゃない？結果を見てみたいな。よろしくね。
その2番目のリンクはBig O記法とは関係ないし、誰のモデルにもならないよ。
遅れての参加だけど、プログラミングをちょっとかじる程度の素人としては、この記事はめちゃくちゃ勉強になったよ。これを読んだからってエキスパートになれるとは思ってないし。Big O記法って今まで聞いたことなかったけど、アルゴリズムの構築をこんな視点で見られるなんて面白いね。完璧で網羅的な説明じゃなきゃダメ、みたいなことだと、相対性理論を知ってる人なんて13人しかいないってことになっちゃうよ。アイデアを紹介して、残りは読者に任せるって内容にも十分価値があると思うな。
ここでの批判は、記事が不完全だからじゃなくて、いくつかの根本的な間違いがあって、実際にはBig O記法をちゃんと説明してないってことだと思うな。「ポップカルチャー版のBig O」をBig O記法として紹介してるだけで、著者がしっかり理解してないまま、いくつか深刻な間違いをしてるんだ。役立たないわけじゃないし、すごく丁寧に作られてるみたいだけどね。プレゼンテーション自体は好きだよ！
O(1)は多くの場合、ハッシュ関数が関わってくるけど、これは自明じゃないけど定数コストなんだ。Nの値が小さい場合は、最悪N^2のアルゴリズムに実測時間で負けることもあるよ。
多くの実用的なアプリケーションでは、Big O記法ってのはかなり貧弱な考え方だと思うんだ。特にメモリアクセスのレイテンシは、だいたいO(log(N))（URL: https://news.ycombinator.com/item?id=12385472 ）とO(N^(1/2))（URL: https://news.ycombinator.com/item?id=12383275 ）の間くらいだね。例えば、ソートされた形式を維持できるアプリケーションだと、ちゃんとしたB+-treeは、ハッシュマップより圧倒的にパフォーマンスが良いことが多いんだ。std::unordered_mapをstd::vector（SoAのために実際は2つくらい）に置き換えることで、C++プログラムを劇的に高速化できた経験があるよ。アイテムを順不同で集めて、ソートしてからハッシュマップの代わりにバイナリ検索を使ったら、その関数は3倍くらい速くなったんだ。これってベクトル化に優しい構造とか、そういうのなしでの話だからね。
確かにそうだけど、n^2が実用的じゃないってこと、あんまり大声で言わない方がいいかもね。ほとんどの場合、n^2はPCが動かなくなるレベルだし。みんなにそれを理解させるのは大変だよ。あと、運が良ければモジュロみたいな完璧なハッシュ関数があることもあるしね。
ちょっと待って、モジュロは完璧なハッシュ関数じゃないよ…。例えばハッシュテーブルのサイズが11で、22と33をハッシュしたらどうなる？最初の話もよくわかんないな。n^2のアルゴリズムはただの多項式だから、大規模な入力でも動かせるはずだよ。2^nと間違えてない？
n^2って多分、最悪のアルゴリズムだよね。本番環境に導入されやすいほどは速いのに、使い始めたらすぐ破綻するほど遅いんだもん。あのRockstarでさえGTAVの読み込みに5分もかかったのは、スタートアップシーケンスにn^2アルゴリズムがあったせいらしいよ。
もっとコメントを表示（1）
＞ モジュロは完璧なハッシュ関数じゃない
いや、intを扱っていて、最大最小の範囲を事前に知ってる場合は完璧なハッシュ関数になるんだよ。範囲が大きすぎなければ、その範囲のサイズでモジュロできるからね。君の例なら33から21を引いて→mod 12って感じ。これは意外とよくあることだけど、何に取り組むかによるよね。ハッシュテーブルを使いたくなるけど、この場合は効率が悪いんだ。
n^2アルゴリズムが“massive”な入力でも動くっていうのは、ちょっと無理があるんじゃない？10億から1000億くらいのデータになると、さすがに厳しくなってくるよ。
Big Oの問題は、1要素あたりの処理時間がわからないと、どれくらいの要素数でどれくらいの時間がかかるか予測できないことだよね。例えば、1要素の処理に10秒かかるとしたら、10要素だと16分になっちゃう。実際には、n^2はもっと手前の1万〜10万くらいのデータ量でも、驚くほど遅くなって数分かかることがあるよ（1要素10msなら、たった77要素で1分かかる計算だね）。
ほとんどの人が扱うには、10億っていうのはかなり大きい数字だと思うな。でも、君の言いたいことはわかったよ。
N^2ってただの二重ループでしょ。2D配列があればどこにでも出てくるじゃん。もし配列のサイズが小さくて速度に影響しないなら、わざわざコードを複雑にする必要あるのかな？
2D配列を二重ループで処理するのはO(N)操作だよ。Nはデータのサイズであって、配列でどう表現されているかは関係ないんだ。
Nが小さいって保証できるなら、多分問題ないんじゃないかな。
“明白”って言われるけど、みんなにとってそうじゃないみたいだね。実際にはほとんどのケースで遅くなるのに、O(1)にしようと書き直してるのを何度も見たことあるよ。
たとえほとんどのケースで遅くても、まれにパソコンがフリーズするような状況を避けられるなら、それでも勝ちだよね。
入力が十分小さければ、Big-Oが何と言おうとパソコンはフリーズしないよ。多くの場合、入力は小さいか、まあまあのサイズであることが保証されてるし。
入力が小さいと保証されてる場合もあるけど、保証されてないのに小さいと仮定されてる場合も多いんだ。そこが問題だよね。古典的な例だと、Windowsのデスクトップアイコン配置アルゴリズムが線形探索のパフォーマンス問題を引き起こしたケースがあるよ。https://github.com/microsoft/Windows-Dev-Performance/issues/…
電気工学を学んだけど、Big O記法ってちゃんと説明された記憶がないんだよね。いつも、もう知ってるでしょ、って感じで流されてた気がする。数学とかコンピューターサイエンスだと、どのレベルで教えるのが一般的なのか気になるな。
うちの大学ではCS専攻の必修で“アルゴリズム分析”っていう授業があったよ。そこでいろんな証明と一緒にBig O記法も扱ってた。でも3年生か4年生の授業だったから、1年生の終わりまでには（たぶん自然に）ある程度知ってるって思われてたと思うな。
関数f(x)がO(g(x))であるって言うのは、f(x)/g(x)が有界であること、つまり、すべてのxに対してf(x)/g(x) ＜ CとなるようなCが存在することだよ。コンピューターサイエンスでは、f(x)はアルゴリズムの特定の操作回数みたいな複雑性関数であることが多いね。
これは補足が必要だね。f(x)がO(g(x))であるって言うのは、あるX ＞= 0が存在して、すべてのx ＞ Xに対してf(x)/g(x)が有界である場合だよ。そうしないと、例えば1がO(x)であるとは言えなくなっちゃうからね。
なんてひどい説明なんだ！実用的な目的で言えば（技術的に間違ってても気にしないけど）、Big O記法はアルゴリズムのコストが入力サイズに対してどう増えるかを記述するものだよ。例えば、入力が1増えるごとにコストが2倍になるならO(n^2)。入力サイズと比例してコストが増えるならO(n)。簡単でしょ。
僕はコンピューターサイエンスの教育は受けてないけど、数学の教育は受けてたよ。だから前の定義は素晴らしい説明だと思ったけど、他の人がそう感じないのも分かるな。でも、あれを決して“ひどい”説明とは言えないと思うよ。
数値解析の分野だと、Big O記法は誤差項の成長率に使われるんだ。コストやアルゴリズムとは関係ない使い方だよ。
入力サイズが1増えるごとにコストが倍になるなら、それはO(2^n)だよ。
これは”技術的に”間違ってるってだけじゃなくて、完全に間違ってるよ。O記法はアルゴリズムとは全く関係ないんだから。
過剰に修正しすぎるのはやめようよ。実際のプログラマーにとって、O記法はもちろんアルゴリズムと関係があるんだから。
コンピュータサイエンスの基礎だよね。一年生で習ったよ。別に難しいことはないさ。アルゴリズムの入力数が増えるにつれて、操作の数がどう増えるかを説明してるだけ。見た目は怖そうだけど、すごくシンプルで分かりやすいよ。
でも、もっと複雑になることもあるよ。アルゴリズムの複雑さにはnだけじゃなくて、Kやρみたいな複数のパラメータがある場合もあるんだ。Big O式でこれらの組み合わせが出てくることも。
そういう場合でも、特定のアルゴリズムの応用でρが上限があるってわかれば、Big OはnとKの影響を強く受けるようになるよ。
このブログ記事は説明しようとして間違ってるよ。シンプルじゃないんだ。例えば、O(2^n)の複雑さを持つアルゴリズムが、O(1)のアルゴリズムより速いことだってあるし、同じアルゴリズムでもサイズ関数の定義の仕方でO(2^n)にもO(n³)にもなりうる。全然分かりやすくなんかないよ。
だから彼は、Big O記法は入力サイズが変わったときに実行時間がどう振る舞うかを説明するのであって、特定の値に対してどう振る舞うかを説明するわけじゃないって言ったんだよ。
俺のデータ構造とアルゴリズムの授業でBig Oを習ったけど、CSの教授やTAは当たり前だと思ってたみたい。
説明は15分くらいで、試験でもコードの正確性に95点、Big Oの複雑性の説明に5点って感じで、おまけみたいな扱いだったな。
僕はCSの離散数学の授業でBig Oをみっちり習ったよ。
それは定義次第で色々変わるからだよ。
例えば、チューリングマシンがアルゴリズムを停止させるのにかかるステップ数として定義するなら、対数時間アルゴリズムなんて存在しない。O(lg n) = O(1)になるんだ。
Log(n)はnより成長が遅い。
つまり、あるNがあって、プロセスがN回未満の状態遷移で停止するってこと。
でもチューリングマシンでは、1回の状態遷移でテープの新しいセルは1つしか読めない。
だから、アルゴリズムは定数時間で停止するんだ。
nとNの関係って何？log(n)はまだ無限に大きくなるはずだから、君のコメントは理解できないんだけど。
もっとコメントを表示（2）
nとNに関係なんてないよ、もちろんNは固定された定数。
Log(n)は無限だけど、もしチューリングマシンがサブ線形時間で停止するなら、ある長さの入力に対して、入力テープの全セルを読む前に停止するってこと。
だから、入力のサイズがどうなろうと、そのTMは定数時間で停止するしかないんだ。わかる？
ごめん、でもやっぱりわからない。TMの知識不足かもしれないけど、O(log n)は定義上全ての入力を読まないよね。
だからって、それが入力サイズと無関係になるわけじゃないと思う。
君のTMが特別なの？
あんまり時間取らせたくないし、俺がバカなのかも。
編集: O(log n)が不可能、少なくともO(n)になるのはなんとなくわかるんだけど、O(1)に減るのは理解できない。
じゃあ、もっと詳しく証明を説明するね。
TMがサブ線形だと仮定する。すると、ある固定されたNが存在して、サイズn ＜= Nの全ての入力に対して、TMが停止するステップ数はN未満になる。
どんな入力Iを考えても、最初のN文字だけを抜き出したI_Nを考えると、TMはI_NでNステップ未満で停止する。
そして、TMのIでの最初のNステップの挙動はI_Nと同じになる。
なぜなら、Nステップで読めるのはせいぜい最初のN文字までで、その範囲では両方の入力は同じだからね。
だから、そのマシンはIでもNステップ未満で停止するはず。
Iは任意に選んだものだから、どの入力に対してもNステップ未満で停止することが示されたね。Nは固定された定数だったのを思い出して。
論理的に問題なさそうだね、ありがとう！
チューリングマシン（TM）は入力が左から右に読まれることを忘れないで。もしTMが長さNの全ての入力で停止する固定数Nがあるなら、TMは追加の入力を読む前に停止するから、長さN+1の入力でも同じステップ数で停止するはずだよ。
＞「もう知ってる前提で流されてる感じがしてた」って意見、わかるなぁ。僕がBig O記法を習ったのは、little-oと一緒に微積分を勉強してた時だったよ。
Big O記法の入門記事を見るたびに、僕は最悪ケースに関するセクションを探しちゃうんだ。ほとんどの記事にある根本的な誤解を見つけるためにね。案の定、この記事にもあったよ。「Big O記法は常に最悪ケースを表す」って書いてあるけど、これは違うよ。携帯からだから詳しく説明できないけど、オンラインには情報がたくさんあるよ。
大丈夫、君が僕に指摘してくれたのは初めてじゃないよ！もっとちゃんとしたデバイスがあるときに、君がどう説明してくれるのか聞きたいなぁ。
O()は必ずしも最悪ケースの振る舞いを記述するわけじゃないよ。それはあくまで漸近的な上限を提供するだけ。だから、二次ソートアルゴリズムもO(n^3)だと言えるけど、それはちょっと誤解を招くかもしれないね。
数学的にはそれは正しいけど、現場のソフトウェアエンジニアは、僕たちが気になるケース（最悪、償却、平均など）で簡単に証明できる、一般的な「最もタイトな」上限という意味で使ってるんだ。実際に可能な最もタイトな上限ってわけじゃないよ。
意味はもう決まってるんだ。それは条件を満たす関数の集合のことだよ。だから、O(n^2)はO(n^3)のサブセットなんだ。
要するに、文脈によって分析が違うってことだよ。最良ケース、平均ケース、最悪ケースの分析ができるんだ。例えば線形探索は最良ケースだとO(1)だね。これは細かい指摘に聞こえるかもしれないけど、だからといって記事が間違ってないわけじゃないんだ。「指摘は初めてじゃないよ！」って言うなら、訂正してくれると嬉しいな。オンラインにはこの間違いをしてる人が多すぎるんだ。
そうだね。この記法はどんな関数がどれだけ速く成長するかを表すのに使えるんだ。それが入力長に関する最悪ケースの実行時間でも、平均ケースの実行時間でも、何でもありだよ。でも、一番よく使われるのは、特に入門コースでは最悪ケース分析だね。記事のΘ記法の説明も間違ってるよ。それは上限と下限、そして最良・最悪ケース分析っていう、2つの異なる直交する概念をごっちゃにしてるんだ。「最良ケースはO(n)」ってフレーズ自体が、「Big O記法は常に最悪ケースを表す」っていう主張と矛盾してるし、記事の中で最良ケースに使ってるのは明らかだね。
「いつも」って言葉のせいで指摘されちゃったんだ。みんなから間違いだって言われるのは本当にへこむよ。一生懸命書いたのにさ。正確な表現を見つけたいから、みんなも僕が人間だってこと忘れないでほしいな。
その2つの違いについて詳しく教えてほしいな。あと、初心者にも分かりやすく記事にどう書けばいいかな？この部分はもう何回も修正してるんだけど、なかなかうまくいかないんだよね。
要は、同じ入力の長さでも中身で実行時間は変わるんだよ。一番遅いケースをずっと選ぶと、ある関数になる。それを上限や下限で評価するんだ。最高のケースでも同じね。関数は一本の線じゃなくて、帯みたいな幅があるって考えたらいいよ。これを記事にするのは難しいけど、頑張って！
自然言語は文脈で意味が変わるもんだよ。「Big O記法」もそう。面接で数学的な意味だけでO(n^3)って答えたら、まず採用されないね。教科書通りじゃなくて、業界の共通語を理解しなきゃ。面接官が間違ってるなんて思っちゃダメだよ。プロダクトと話すともっと大変だよ。
Big O記法が今の意味になったのは、バカだからじゃないと思うよ。数学には「十分速い」近似的なタイトな上限って言葉がないんだ。Big Thetaは下限の証明も必要で厳しすぎるしね。だから、実用的な目的で、厳密すぎないけど「十分タイトな上限」を表すのにBig Oが選ばれて、それが業界の共通語になったんだ。
二次ソートアルゴリズムがO(n^3)って言われるのは、どういうこと？全然ピンとこないから、もっと詳しく聞きたいな。
説明してくれて本当にありがとう。今書いてる記事は、厳密には正確じゃないかもしれないけど、ブートキャンプを出たばかりでCSの知識がない初心者にとっては、これで十分合理的だと思うんだ。彼らが理解できるように書くのが僕の目標だからね。
f(n)がO(g(n))って書くとき、もうすでにfが「入力サイズnの問題での最大ステップ数」、つまり最悪ケースを表してるってことなんだ。O(g(n))ってのは、fがg(n)である定数倍まで漸近的に上限されるって意味だよ。
うんちく言う人には「ほとんどいつも」って言えばいいよ。Big O記法は最良ケースとか平均ケースにも使うんだけど、みんなそこまで気にしないだけなんだ。
