【じかんけいさんりょう】

時間計算量とは？

最終更新: 2026年10月2日

💡 データが増えたとき、計算の手間がどう増えるか

入力が増えたとき、アルゴリズムの計算に必要な手間がどう増えるかを表す指標。O記法、最悪・平均の場合、実測時間との違いを小さなループの例で解説します。

📌 このページのポイント

n回のループと、内側・外側ともn回のループの比較です。色は二つの数え方を区別します。所要時間が同じ倍率になることや、小さい入力での速さの順位は示していません。

ひよこ

時間計算量は、何秒かかるかのこと？

ペンギン先生

入力が増えたとき、計算の手間がどのように増えるかを考える指標だよ。例えばn個の要素を1回ずつ見るなら、見る回数はn回。実際の秒数は、機器や実装にも左右される。

ひよこ

O(n)は、ちょうどn回という意味？

ペンギン先生

ちょうどとは限らない。O記法は、十分大きなnについて、定数倍を除いた増え方の上限を表す。3n+4回の処理もO(n)と言える。厳密には、それをO(n²)と書くこともできるので、通常は役立つ小さい上限を示す。

ひよこ

O記法は、必ず最悪の場合を表す？

ペンギン先生

記法自体に最悪という意味はない。ある処理の最悪の場合をO(n)と表すことも、平均の場合をO(n)と表すこともある。入力の条件と、どの場合を分析しているかを一緒に読む必要がある。

ひよこ

二重ループなら、必ずO(n²)？

ペンギン先生

内側も外側もn回ずつ動く例なら、内側の処理はn²回だ。ただし、内側が常に3回なら全体は3n回。ループの見た目だけでなく、実際の繰り返し回数を数えるんだ。

ひよこ

O(n)なら、O(n²)よりいつも速い？

ペンギン先生

いつもとは言えない。小さい入力では定数倍や準備の手間が効くこともある。O記法で大きな入力への伸び方を比較し、実際に扱うデータでは測定する、という使い分けが大切だよ。

もっと詳しく知りたい人へ

O記法とΘ記法はどう違う？

Oは漸近的な上限、Θは上限と下限の両方で同じ増え方に挟める、より厳密な目安です。例えば3n+4はO(n)でありΘ(n)でもあります。初心者はまず、O記法を「正確な回数や秒数の公式」と読まないことが大切です。

いいえ。図は決められたループの内側で行う処理だけを数えています。ループの判定や初期化などを含む全操作の数ではなく、1回の処理にかかる時間も環境で変わります。大きな入力での増え方を比べる例です。

まとめ：ざっくりこれだけ覚えればOK！

「時間計算量」って出てきたら「データが増えたとき、計算の手間がどう増えるか」と思えばだいたいOK！

📖 おまけ：英語の意味

「Time Complexity」＝時間計算量

💬 入力の大きさに対して必要な時間資源を考えます。説明では比較や繰り返しの回数などを数えることがあります。