Big O Notation: シンプルなガイド

ビッグ O 記法は、入力サイズが増大するにつれて時間と空間の観点からアルゴリズムのパフォーマンスや複雑さを記述するために使用される数学的概念です。これは、入力が大きくなるとアルゴリズムの実行時間がどのように増加するかを理解するのに役立ち、さまざまなアルゴリズムのより標準化された比較が可能になります。

Big O 記法を使用する理由

アルゴリズムを比較する場合、実行時間だけに依存すると誤解を招く可能性があります。たとえば、あるアルゴリズムでは大規模なデータセットを 1 時間で処理する場合もあれば、別のアルゴリズムでは 4 時間かかる場合もあります。ただし、実行時間はマシンやその他の実行中のプロセスによって異なる場合があります。代わりに、Big O Notation を使用して実行された操作の数に焦点を当て、より一貫した効率の尺度を提供します。

例: 数値の合計

1 から n までのすべての数値の合計を計算する 2 つの方法を見てみましょう:

オプション 1: ループの使用

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

オプション 2: 数式を使用する

function addUpTo(n) {
    return n * (n + 1) / 2;
}

複雑さを分析する

オプション 1 では、n が 100 の場合、ループは 100 回実行されます。対照的に、オプション 2 では、常に一定数の演算 (乗算、加算、除算) が実行されます。したがって:

• オプション 1 は O(n) です: 時間計算量は n に応じて線形に増加します。
• オプション 2 は O(1): 入力サイズに関係なく、時間計算量は一定のままです。

免責事項

オプション 2 には 3 つの演算 (乗算、加算、除算) が含まれますが、Big O 分析の一般的な傾向に焦点を当てます。したがって、O(3n) として表現する代わりに、O(n) に簡略化します。同様に、O(n 10) は O(n) に簡略化され、O(n^2 5n 8) は O(n^2) に簡略化されます。 Big O Notation では、最上位の項がパフォーマンスに最も大きな影響を与える最悪のシナリオを考慮します。

O(log n) で表される対数時間計算量など、上記の一般的な計算量以外の表記形式もあります。

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

Big O Notation を使用すると、入力サイズに基づいてアルゴリズムの実行時間の増加を形式化できます。特定の操作数に焦点を当てるのではなく、アルゴリズムを次のようなより広範なクラスに分類します。

• 一定時間: O(1) - アルゴリズムのパフォーマンスは入力サイズによって変化しません。
• 線形時間: O(n) - パフォーマンスは入力サイズに応じて線形に増加します。
• 二次時間: O(n^2) - 入力サイズが増加するにつれて、パフォーマンスは二次的に増加します。

O(n^2)の例

0 から n までの数値のすべてのペアを出力する次の関数を考えてみましょう。

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

この場合、関数には 2 つのネストされたループがあるため、nnn が増加すると、演算数は二次関数的に増加します。 n= 2 の場合は 4 つの演算があり、n=3 の場合は 9 つの演算があり、O(n^2) になります。

別の例: カウントアップとカウントダウン

function addUpTo(n) {
    return n * (n + 1) / 2;
}

一見すると、2 つのループが含まれているため、これは O(n^2) であると思われるかもしれません。ただし、両方のループは独立して実行され、n に応じて線形にスケールします。したがって、全体的な時間計算量は O(n) です。

分析の簡素化

コードの複雑さのあらゆる側面を分析することは複雑になる可能性がありますが、いくつかの一般的なルールによって物事を簡素化できます。

• 算術演算は定数時間とみなされます。
• 変数の割り当ては定数時間です。
• 配列 (インデックスによる) またはオブジェクト (キーによる) の要素へのアクセスは定数時間です。
• ループの場合、複雑さはループの長さとループ内で起こる複雑さの積です。

空間の複雑さ

ここでは時間計算量に焦点を当ててきましたが、Big O を使用して空間 (メモリ) 計算量を計算することもできます。計算に入力サイズを含める人もいますが、多くの場合、アルゴリズムに必要な空間だけに焦点を当てたほうが便利です。それ自体。

空間の複雑さのルール (JavaScript に基づく):

• ほとんどのプリミティブ値 (ブール値、数値など) は定数スペースです。
• 文字列には O(n) スペースが必要です (n は文字列の長さです)。
• 参照型 (配列、オブジェクト) は通常 O(n) です。ここで、n は配列の長さ、またはオブジェクト内のキーの数です。

例

function printAllPairs(n) {
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            console.log(i, j);
        }
    }
}

この関数では、入力サイズに関係なく一定量の空間 (2 つの変数) を使用するため、空間複雑度は O(1) です。

新しい配列を作成する関数の場合:

function countUpAndDown(n) {
    console.log("Going up!");
    for (var i = 0; i < n; i++) {
        console.log(i);
    }
    console.log("At the top!\nGoing down...");
    for (var j = n - 1; j >= 0; j--) {
        console.log(j);
    }
    console.log("Back down. Bye!");
}

ここでは、入力配列のサイズに応じて増加する新しい配列にスペースを割り当てるため、スペースの複雑さは O(n) です。

結論

Big O Notation は、ハードウェアや特定の実装の詳細に依存しない方法でアルゴリズムの効率を分析するためのフレームワークを提供します。これらの概念を理解することは、特にデータ サイズが大きくなる場合に、効率的なコードを開発するために重要です。パフォーマンスがどのように拡張されるかに焦点を当てることで、開発者はアプリケーションでどのアルゴリズムを使用するかについて情報に基づいた選択を行うことができます。

以上がBig O Notation: シンプルなガイドの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。