O(n²)とは
アルゴリズム / 計算量
要点
O(n²)は、入力データが増えると、処理量がおおよそその二乗に比例して増えることを表します。
O(n²)の意味と、データが増えたときに処理量がどのように増えるのかを、数字を使って整理します。
身近な例で考える
全員がほかの全員と一度ずつ確認し合う場面に似ています。人数が増えると、確認する組み合わせが急に増えます。
正式な意味
入力の大きさをnとしたとき、処理時間や処理回数の増え方がn²を上限の目安として表せる計算量です。
- 英語：
- Quadratic Time Complexity
- 読み方：
- オーダー・エヌ二乗
混同されやすい言葉： O(n)、O(n log n)
データが10倍になると、処理量はおよそ100倍になる
nは、処理するデータの件数など、入力の大きさを表します。処理量がn²に比例して増える場合、10件なら100、100件なら10,000というように、入力が増えるほど処理量が急に大きくなります。
- データが10倍になると、処理量はおよそ100倍
- データが100倍になると、処理量はおよそ10,000倍
- データが少ない間は問題が見えず、本番の規模で遅くなることがある
二重の繰り返しで現れやすい
すべてのデータについて、もう一度すべてのデータを調べるような処理では、O(n²)になりやすくなります。ただし、二重ループがあれば必ずO(n²)になるわけではありません。内側の処理回数や、途中で終了する条件によって増え方は変わります。
実際の処理回数そのものではない
この説明を書くときに確認した情報
できるだけ公式資料や原著論文を確認しています。
- 公式資料・MIT OpenCourseWareMIT 6.006 Introduction to Algorithms — Lecture 1
最終確認: 2026-08-09