概念 / 計算量の概念

計算量は、
データが増えたときに
どれだけ大変になるか。

計算量は、プログラムの大変さを表す目安です。まずは『Big-O は計算量を書くための記号』だと捉えれば十分です。

まずは Big-O増え方を見る初学者向け導入

このページの目次

このページでわかること概要考え方の流れ要点まとめ動きで確認次に見るページ

このページでわかること

先に知っておくポイント

1. 計算量は処理回数の増え方を見る

2. Big-O はその書き方のひとつ

3. 小さい入力では差が見えにくい

概要

計算量は、プログラムの大変さを表す目安です。まずは『Big-O は計算量を書くための記号』だと捉えれば十分です。

What Is Complexity

計算量は「大変さ」の目安

計算量とは、そのプログラムがどれくらいたくさん仕事をするかを表す目安です。

ここでいう仕事とは、たとえば『何回比べるか』『何回探すか』『何回入れ替えるか』のような回数のことです。

つまり計算量は、プログラムの速さを直接書くというより、『仕事量がどう増えるか』を見るためのものです。

Big-O

Big-O は計算量を書くための記号

Big-O は、計算量を書くときによく使う記号です。O(n) や O(n²) のように書きます。

大切なのは、Big-O 自体がアルゴリズムの名前ではなく、『計算量を表す書き方』だということです。

最初は『データが増えたとき、仕事量がどんなふうに増えるかを書く記号』と考えれば十分です。

Why Growth Matters

なぜ「増え方」を見るのか

10件のデータでは、どの方法もすぐ終わるように見えることがあります。

でも 1000件、10000件と増えていくと、方法によって仕事量の増え方に大きな差が出ます。

その差を見るために、計算量では『今どれくらい速いか』より『増えたときにどうなるか』を重視します。

Concrete Examples

よく出る3つの形

O(log n)

候補を半分ずつ減らす形です。データが増えても、仕事量は少しずつしか増えません。

O(n)

1つずつ順に見る形です。データが2倍になると、仕事量もだいたい2倍になります。

O(n²)

全体を何度も見比べる形です。データが増えると、仕事量が急に大きくなります。

How To Read

O(n) や O(n²) はどういう意味？

O(1)

データが増えても、仕事量がほとんど増えない。

O(n)

データが2倍なら、仕事量もだいたい2倍。

O(n²)

データが2倍になると、仕事量は4倍くらい。

Important Note

今速く見えても油断しない

10件や20件くらいの小さいデータでは、O(n) と O(n²) の差があまり目立たないことがあります。

だから、小さいデータでたまたま速く見えたとしても、それだけで良い方法だと決めないことが大切です。

データが増えたときにどうなるかまで見て、はじめて方法の違いがわかります。

Common Mistakes

初学者が誤解しやすい点

O(n²) は『n² 秒かかる』という意味ではない
今の入力で速かったことと、大きい入力でも強いことは別
Big-O は便利だが、平均ケースや定数倍を完全に無視してよいわけではない
アルゴリズムによっては最良・平均・最悪を分けて考える必要がある

考え方

考え方の流れ

入力サイズ n を大きくして考える
処理回数がどう増えるかを見る
その増え方を Big-O で表す
O(log n), O(n), O(n²) の違いを比べる

要点

要点まとめ

計算量

処理回数の増え方

Big-O

計算量の表し方

まず見る差

増え方がゆるやかか、急か

最初の目標

違いを感覚でつかむ

補足

向いている場面と注意点

ここだけ覚える

計算量は『どれだけ仕事が増えるか』、Big-O は『その増え方の書き方』です。

見方

まずは『データが2倍になったら、仕事量は何倍くらいになるか』で考えると理解しやすいです。

注意

O(n²) は『n²秒』という意味ではありません。処理回数の増え方を表しています。

動きで確認

動きを見てたしかめる

ここでは「計算量は処理回数の増え方を見る」を見ながら、上で読んだ内容を動きと結びつけます。

ゆるやか急増安定

次に見る

次に見るページ

比較すると違いがわかりやすいページを先に置いています。

Bubble Sort（バブルソート）を見る Selection Sort（選択ソート）を見る

計算量は、データが増えたときにどれだけ大変になるか。