ハクソク

世界を動かす技術を、日本語で。

ビッグO記法の視覚的入門

274日前原文(samwho.dev)

概要

  • Big O記法 は、入力サイズに対するアルゴリズムの性能や成長率を表現する手法
  • O(1) （定数時間）、 O(log n) （対数時間）、 O(n) （線形時間）、 O(n^2) （二乗時間）など、代表的な4つのカテゴリを解説
  • sum関数 や bubble sort、 binary search などの具体例で理解を深める構成
  • 最悪ケース を基準とした計算量評価が基本
  • 実践的な改善策 や注意点も紹介

Big O記法の基礎

  • Big O記法 は、関数やアルゴリズムの 性能（計算量） を、実際の処理時間ではなく 入力サイズの増加に対する成長率 で表現
  • 時間計測ではなく、 入力nが増えたときに処理量がどのように増えるか を分析
  • 主に プログラムやアルゴリズムの効率性比較、大規模データへの対応力評価に利用
  • O(1) （定数）、 O(log n) （対数）、 O(n) （線形）、 O(n^2) （二乗）など、成長率で分類
  • 最悪ケース （worst-case）を基準に評価するのが一般的

線形時間（O(n)）の例：sum関数

  • sum(n)関数は 1からnまでの合計値をforループ で計算
  • 入力nが2倍になると、 実行時間もほぼ2倍 となる特徴
  • このように 入力サイズに比例して処理回数が増加 するものを O(n) と呼称
  • O(n) の「O」は Order（成長の階級） を意味し、 O(n) は「nの階級の成長」を示す
  • Big O記法 では 最小の項のみ を記述し、O(2n)やO(n+1)とは書かない

定数時間（O(1)）の例：数式によるsum関数

  • sum(n)を数式(n*(n+1))/2で計算すると、 入力サイズnに関係なく一定回数の演算 で完了
  • どんなnでも 処理時間はほぼ変わらない ため、 O(1) （定数時間）と呼ぶ
  • O(1) は「瞬時」ではなく「入力サイズに依存しない」ことを意味
  • 実際の処理時間が長い場合もあり得る点に注意

二乗時間（O(n^2)）の例：bubble sort

  • bubble sort は、隣接要素を比較・交換しながら 複数回ループ して整列
  • 最悪ケース（逆順配列）では n回のループをn回繰り返す ため、 O(n^2) （二乗時間）となる
  • 入力データの並び順 によって実行回数が変わるが、Big O記法では 最悪ケース を基準
  • O(n^2) は大量データに弱いアルゴリズムの典型例

対数時間（O(log n)）の例：binary search

  • binary search は、整列済み配列から 中央値で範囲を半分に絞り込む探索法
  • 各ステップごとに探索範囲が1/2 になるため、必要なステップ数は log₂n に比例
  • 例：1～1,000,000,000の中から1つを当てる場合でも 最大31回の比較 で済む
  • O(log n) は大規模データでも極めて効率的なアルゴリズムの代表

実践的なBig O活用例と注意点

リスト内検索

  • 配列で値を探すcontains(items, target)は O(n) （線形探索）
  • 頻繁に検索する場合、 Set構造 を使えば O(1) で高速化可能
  • ただし、new Set(items)の生成自体は O(n) である点に注意

インデックス付きループの罠

  • ループ内でitems.indexOf(item)を呼ぶと、 O(n)の探索×n回＝O(n^2) となり非効率
  • ループインデックスやforEach((item, index) => ...)を活用し、 O(n) へ最適化

再帰とキャッシュ

  • 再帰的な計算 （例：factorial）は O(n) だが、同じ計算を繰り返す場合は メモ化（キャッシュ） で高速化可能
  • 再帰呼び出しの最適化やキャッシュ利用で 計算量の削減 を図る

まとめ

  • Big O記法 は、アルゴリズムのスケーラビリティを理解・比較するための 強力な指標
  • O(1)、O(log n)、O(n)、O(n^2) の違いを体感し、 適切なアルゴリズム選択・改善 が可能
  • 最悪ケースの計算量 を意識しつつ、 現実的なパフォーマンス も考慮した設計が重要

Hackerたちの意見

ビッグO記法を身につけるための一番効果的な方法は、日常の経験に結びつけることだと思う。

いいね！ピンを送ったけど、ちゃんと届いてるといいな。ちょっとドーパミンが出た気分 ;-)

└

届いたよ、ありがとう！<3

ダイナミックなビジュアライゼーションが内容を理解するのにめっちゃ役立つね。こんなレッスンをもっと作ってほしい！

└

気に入ってもらえて嬉しい！<3

電気工学を学んでたけど、ビッグO記法がちゃんと説明されたことがなかった気がする。毎回紹介されるときに見逃してたのかな？いつも「これくらいは知ってるよね」って感じで流されてた。どのレベルの数学やコンピュータサイエンスが普通はこれを紹介するのか気になる。

└

僕の大学には「アルゴリズム分析」の授業があって、これはCS専攻には必須だったんだ。いろんな証明方法もカバーしてたけど、これは3年生か4年生の授業だったよ。1年生の終わりまでには、ある程度この概念に慣れてることが期待されてたと思う（なんか自然に覚える感じでね）。

└

関数 f(x) が O(g(x)) であると言われるのは、f(x)/g(x) が有界で、つまり C という値があって、すべての x に対して f(x)/g(x) < C になるときだよ。コンピュータサイエンスでは、f(x) はしばしばアルゴリズムを完了させるときの特定の操作の数みたいな複雑度関数になることが多い。

└

コンピュータサイエンス101。1年生のときに学んだよ。実際、そんなに難しいことはないんだ。ただ、アルゴリズムの入力数が増えるにつれて、操作の数がどう成長するかを説明してるだけだから。見た目は怖いけど、すごくシンプルでわかりやすいよ。

あなたのブログはいつも情報満載のビジュアライゼーションがあって、こういう概念を理解しやすくしてくれる！どのツールを使って作ってるの？

└

コードはここにあるよ: https://github.com/samwho/visualisations。今回は基本的なJS、CSS、HTMLしか使ってないんだ。確か、唯一の外部依存はJavaScriptをASTにパースするためのやつだったかな。

ビッグO記法についてのスレが立つたびに、誰かがアニメ「ザ・ビッグO」との関連をわかりやすく説明してくれることを期待してる。あのショーで何が起こったのか、まだ理解できてないんだよね。

└

（ビールを4本飲み干す）さて、つまり、パシフィック・リム、ダークシティ、マトリックスを全部混ぜたような感じだね。順番はその通りで。

この記事とその関連のHNコメントセクションは、ビッグO記法の説明者たちの長い伝統を引き継いでるね [0]。こういう記法の細かい技術的なポイントと実際の使い方についてコメントで揉めるのもお決まりだしね [1]。時代は繰り返す… [0] https://nedbatchelder.com/text/bigo.html [1] https://nedbatchelder.com/blog/201711/toxic_experts.html

└

へへ、そうだよ、ネッドがこの前素敵なメールを送ってくれたんだ。自分の役割を果たせて嬉しいよ。

└

その記事の教訓は、誤解を招く説明を訂正しようとするのをやめるべきだってことじゃなくて、ネット上の一部の人たち（そこに書かれている「専門家」みたいな）は、著者を優しく助けるよりも「戦い」を挑んで勝つことに興味があるってことだと思う。Pyonのコメントを見ると、彼はすごく攻撃的でネットのトロールみたいだったよ。この点を誤解するのは「…だから、技術的な詳細は重要じゃなくて、不正確でも大丈夫」ってことになる。

└

その2つ目のリンクはビッグOについてじゃないし、誰もそれをモデルにすべきじゃないよ。

└

最初の投稿のコメントを読んだ限りでは、Pyonはすごく有害で細かすぎる感じだけど、Nedの反論もあまり良くないね。例えば、反論の中でその細かすぎる技術的な詳細が実際に説明されてるところはどこにもない。実際、説明がすごく不自然で、ただ「特定の詳細」と繰り返して言ってるだけなんだ。私の見解では、著者はやりすぎてると思う。彼はPyonを批判の伝え方（それは有害だった）だけでなく、批判の内容（なんで？）でも軽視してる。結局、Nedはオンラインでの共感とコミュニケーションについては正しいんだけど、教育者としては、Pyonの指摘がなぜ不必要に技術的で細かすぎると思ったのか、少しでも聞けたら良かったな。代わりに「何十年も働いてきたけど知らなかった」って言ってるだけ。誰も学ぶのに経験しすぎることはないから。追記：PyonとNedの元のコメントセクションをざっと見たけど、Nedはかなり外交的でPyonの批判に知的に応じてるみたい。なんでこのレベルの分析がその後のブログ記事には全然ないの？技術的な詳細や重要性を理解できてない自分としては、要約された分析を聞けたら嬉しいな…

ビジュアライゼーションが大好き！何年も前にこれらのアルゴリズムを学んだ僕にとっても、視覚化されるのを見るのは嬉しいね！

O(1) は多くの場合、ハッシュ関数を含むんだけど、これは非自明だけど定数コストなんだ。Nの値が小さいときは、最悪ケースのアルゴリズム n^2 に時間で負けることもあるよ。

└

まあ、確かにそうなんだけど、大声で言わない方がいいよ。誤解されちゃうから。実際のところ、n^2って言うと、ここではコンピュータが動かなくなるってことだからね。それを理解させるのはもう大変だし ;) それに、運が良ければ、モジュロみたいなトリビアルな完璧ハッシュがあるし。

驚くのは、原子の数に対してO7で成長する量子計算があって、科学者たちはNが小さいからそれを実行するのを問題視してないってこと。コンピュータは常に速くなってメモリも増えてるし、結果は価値があるからね。（コンピュータサイエンスの専門家じゃないから、O(n)の用語を標準と違う使い方してたらごめんね。）