二次時間 O(n²) — ネストループが支配するとき
O(n²)二次時間計算量を理解し、ネストループがそれを引き起こす理由、認識と回避の方法を学びます。バブルソート、選択ソート、行列操作をカバー。
Complexity Classes
詳細な説明
O(n²)二次時間とは？
アルゴリズムがO(n²)とは、実行時間が入力サイズの二乗に比例して増加することを意味します。典型的な原因は2つのネストループです。
成長率
| n | n² |
|---|---|
| 100 | 10,000 |
| 1,000 | 1,000,000 |
| 10,000 | 100,000,000 |
O(n²)を回避する方法
- ハッシュテーブルを使用 — ネスト検索を避ける：O(n²)の代わりにO(n)
- 先にソート — その後バイナリサーチまたはツーポインタを使用
- 分割統治 — O(n log n)に削減
- 動的計画法 — 重複する部分問題の再計算を回避
ユースケース
二次計算量の理解は、パフォーマンスボトルネックの認識に不可欠です。コードレビューで不要なO(n²)ネストループを見つけ、O(n)またはO(n log n)に置き換えることは、最も影響の大きい最適化の一つです。