Elegant Access

今日のトピック

トピック: Big-O記法
難易度: 初級
カテゴリー: アルゴリズム基礎

概念学習

核心概念

Big-O記法は、アルゴリズムの時間計算量または空間計算量の上限を表す数学的記法です。最悪のケースを表し、入力サイズが増加したときにアルゴリズムがどのようにスケールするかを理解するのに役立ちます。

重要な原則：Big-Oは成長率に焦点を当て、正確な実行時間ではありません。

定数を無視：O(2n) → O(n)
低次の項を無視：O(n² + n) → O(n²)
nが無限大に近づくときの振る舞いを考慮

一般的な時間計算量（速い順）

O(1) - 定数時間
- 配列要素へのインデックスアクセス
- ハッシュテーブルの検索
- 例：array[5]、map.get(key)
O(log n) - 対数時間
- ソート済み配列での二分探索
- バランスツリーの操作
- 例：検索空間を半分にして要素を探す
O(n) - 線形時間
- 配列を一度反復処理
- 線形探索
- 例：for (int i = 0; i < n; i++)
O(n log n) - 線形対数時間
- 効率的なソートアルゴリズム（マージソート、クイックソート、ヒープソート）
- 例：配列のソート
O(n²) - 二次時間
- 配列を反復処理するネストされたループ
- バブルソート、選択ソート、挿入ソート
- 例：すべての要素を他のすべての要素と比較
O(2^n) - 指数時間
- 部分問題を解く再帰アルゴリズム
- 例：ナイーブなフィボナッチの再帰解法
O(n!) - 階乗時間
- すべての順列の生成
- 巡回セールスマン問題のブルートフォース解法

重要ポイント

定数を削除：O(2n) = O(n)、O(1000) = O(1)
非支配項を削除：O(n² + n) = O(n²)、O(n + log n) = O(n)
異なる入力には異なる変数を使用：2つの配列を処理する場合、O(n)ではなくO(a + b)を使用
Big-Oは最悪のケースを表す（特に指定がない限り、最良のケースはBig-Ω、平均のケースはBig-Θ）
空間計算量も同じルールに従いますが、メモリ使用量を測定

実践的な比較

n = 1,000,000の場合：

O(1)：1回の操作
O(log n)：約20回の操作
O(n)：1,000,000回の操作
O(n log n)：約20,000,000回の操作
O(n²)：1,000,000,000,000回の操作（遅すぎる！）

実装例

O(1) - 定数時間

fun getFirstElement(array: Array<Int>): Int {
    return array[0]  // 配列サイズに関係なく常に同じ時間
}

O(n) - 線形時間

fun findMax(array: Array<Int>): Int {
    var max = array[0]
    for (element in array) {  // n回ループ
        if (element > max) {
            max = element
        }
    }
    return max
}

O(n²) - 二次時間

fun printPairs(array: Array<Int>) {
    for (i in array.indices) {          // n回
        for (j in array.indices) {      // 各iに対してn回
            println("${array[i]}, ${array[j]}")
        }
    }
    // 合計：n * n = n²回の操作
}

O(log n) - 対数時間

fun binarySearch(array: Array<Int>, target: Int): Int {
    var left = 0
    var right = array.size - 1
    
    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            array[mid] == target -> return mid
            array[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }
    return -1
    // 各反復で検索空間が半分になる
}

重要な詳細

よくある誤解

O(n)が常にO(n²)より優れているわけではない：小さい入力では定数が重要
計算量が良い = 実際に速いではない：定数1000のO(n)は、定数1のO(n²)より小さいnで遅い可能性がある
空間と時間のトレードオフ：より良い時間計算量を達成するためにより多くのメモリを使用することがある

最適化すべき時

大きなデータセット（n > 10,000）
頻繁に実行されるコード
リアルタイムシステム
小さいnの場合、可読性 > 最適化

分析のヒント

ループとその反復回数を特定
ネストされた操作を確認
再帰呼び出しの深さと分岐を考慮
入力サイズに関して操作を数える
nが大きくなるにつれて支配的な項に焦点を当てる

今日の振り返り

重要な収穫：

アルゴリズムを選択する際は常に入力サイズを考慮する
O(n)ループ内のO(1)操作はO(n)の全体計算量を作成
ネストされたループはしばしばO(n²)以上につながる - 避けるように努める

関連する概念：

空間計算量分析
最良/平均/最悪のケース分析（Big-Ω、Big-Θ）
償却時間計算量
分割統治アルゴリズムのマスター定理

アルゴリズム日記

アルゴリズム日記 - Big-O記法