初心者のための Big O Notation: 実践ガイド-Python チュートリアル-php.cn

初心者のための Big O Notation: 実践ガイド

DDD

リリース： 2025-01-05 04:12:42

オリジナル

294 人が閲覧しました

Big O Notation for Beginners: A Practical Guide

他のコードがクロールしているのに、なぜ一部のコードが非常に高速に実行されるのか疑問に思ったことはありますか? Big O Notation を入力してください。開発者がアルゴリズムの効率性を議論するために使用する秘密の言語です。簡単に説明してみましょう。

ビッグオー記法とは何ですか?

Big O Notation は、入力サイズの増加に応じてコードのパフォーマンスがどのように拡張されるかを説明します。これは、実行する作業を増やしたときに、コードにどれだけ時間がかかるかを測定するものだと考えてください。

一般的な Big O の複雑さ

O(1) - 一定時間

パフォーマンスの聖杯。入力がどれほど大きくなっても、操作には同じ時間がかかります。

function getFirstElement(array) {
    return array[0];  // Always one operation
}

ログイン後にコピー

O(log n) - 対数時間

通常、問題を毎回半分に分割するアルゴリズムで見られます。二分探索は典型的な例です。

function binarySearch(sortedArray, target) {
    let left = 0;
    let right = sortedArray.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (sortedArray[mid] === target) return mid;
        if (sortedArray[mid] < target) left = mid + 1;
        else right = mid - 1;
    }

    return -1;
}

ログイン後にコピー

O(n) - 線形時間

パフォーマンスは入力サイズに比例して増加します。各要素を一度調べる必要があるアルゴリズムで一般的です。

function findMax(array) {
    let max = array[0];
    for (let i = 1; i < array.length; i++) {
        if (array[i] > max) max = array[i];
    }
    return max;
}

ログイン後にコピー

O(n log n) - 線形時間

マージソートやクイックソートなどの効率的な並べ替えアルゴリズムでよく見られます。

function mergeSort(array) {
    if (array.length <= 1) return array;

    const mid = Math.floor(array.length / 2);
    const left = mergeSort(array.slice(0, mid));
    const right = mergeSort(array.slice(mid));

    return merge(left, right);
}

ログイン後にコピー

O(n²) - 二次時間

ネストされたループで一般的です。入力サイズが大きくなると、パフォーマンスが急速に低下します。

function bubbleSort(array) {
    for (let i = 0; i < array.length; i++) {
        for (let j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                [array[j], array[j + 1]] = [array[j + 1], array[j]];
            }
        }
    }
    return array;
}

ログイン後にコピー

効率的なコードを書くための実践的なヒント

可能な限りネストされたループを避ける
- ネストされた反復ではなく、ルックアップにハッシュテーブルを使用します
- まず並べ替えで問題を解決できるかどうかを検討してください
適切なデータ構造を選択してください
- 高速アクセスを備えた順序付けされたデータの配列
- クイックルックアップ用のハッシュテーブル
- ソートされたデータを維持するためのバイナリツリー
空間と時間のトレードオフ
- より多くのメモリを使用すると、時間の複雑さが大幅に改善される場合があります
- 頻繁にアクセスされる値をキャッシュする

よくある落とし穴

隠しループ

// Looks like O(n), actually O(n²)
array.forEach(item => {
    const index = anotherArray.indexOf(item);  // indexOf is O(n)
});

ログイン後にコピー

ループ内の文字列連結

// Poor performance
let result = '';
for (let i = 0; i < n; i++) {
    result += someString;  // Creates new string each time
}

// Better approach
const parts = [];
for (let i = 0; i < n; i++) {
    parts.push(someString);
}
const result = parts.join('');

ログイン後にコピー