ビッグ O 記法は、入力サイズが増大するにつれて時(shí)間と空間の観點(diǎn)からアルゴリズムのパフォーマンスや複雑さを記述するために使用される數(shù)學(xué)的概念です。これは、入力が大きくなるとアルゴリズムの実行時(shí)間がどのように増加するかを理解するのに役立ち、さまざまなアルゴリズムのより標(biāo)準(zhǔn)化された比較が可能になります。

Big O 記法を使用する理由

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

例: 數(shù)値の合計(jì)

1 から n までのすべての數(shù)値の合計(jì)を計(jì)算する 2 つの方法を見てみましょう:

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

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

オプション 2: 數(shù)式を使用する

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

複雑さを分析する

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

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

免責(zé)事項(xiàng)

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

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

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

Big O Notation を使用すると、入力サイズに基づいてアルゴリズムの実行時(shí)間の増加を形式化できます。特定の操作數(shù)に焦點(diǎn)を當(dāng)てるのではなく、アルゴリズムを次のようなより広範(fàn)なクラスに分類します。

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

O(n^2)の例

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

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

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

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

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

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

分析の簡(jiǎn)素化

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

• 算術(shù)演算は定數(shù)時(shí)間とみなされます。
• 変數(shù)の割り當(dāng)ては定數(shù)時(shí)間です。
• 配列 (インデックスによる) またはオブジェクト (キーによる) の要素へのアクセスは定數(shù)時(shí)間です。
• ループの場(chǎng)合、複雑さはループの長(zhǎng)さとループ內(nèi)で起こる複雑さの積です。

空間の複雑さ

ここでは時(shí)間計(jì)算量に焦點(diǎn)を當(dāng)ててきましたが、Big O を使用して空間 (メモリ) 計(jì)算量を計(jì)算することもできます。計(jì)算に入力サイズを含める人もいますが、多くの場(chǎng)合、アルゴリズムに必要な空間だけに焦點(diǎn)を當(dāng)てたほうが便利です。それ自體。

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

• ほとんどのプリミティブ値 (ブール値、數(shù)値など) は定數(shù)スペースです。
• 文字列には O(n) スペースが必要です (n は文字列の長(zhǎng)さです)。
• 參照型 (配列、オブジェクト) は通常 O(n) です。ここで、n は配列の長(zhǎng)さ、またはオブジェクト內(nèi)のキーの數(shù)です。

例

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

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

新しい配列を作成する関數(shù)の場(chǎng)合:

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!");
}

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

結(jié)論

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

以上がBig O Notation: シンプルなガイドの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國(guó)語 Web サイトの他の関連記事を參照してください。