Big O 記法を理解する: 時間と空間の複雑さに関する初心者向けガイド

同じコードを書くのにさまざまな方法があると想像してください。どれが最も優れているかをどのように判断すればよいでしょうか?そこで Big O 記法が登場します。Big O 記法は、コードに必要な時間とスペースを測定するのに役立ち、比較が容易になります。

Big-O記法とは何ですか?

「オーダー オブ」とも呼ばれるビッグ オーは、最悪のシナリオでアルゴリズムの実行にかかる時間を表す方法です。これにより、入力サイズに基づいてアルゴリズムに必要な最大時間がわかります。これを O(f(n)) と書きます。ここで、f(n) は、入力サイズ n の問題を解くためにアルゴリズムが必要なステップ数を示します。

例で理解してみましょう「文字列入力を受け入れ、反転したコピーを返す関数を作成します」

ご覧のとおり、スタック オーバーフロー ソリューションと上の画像を共有します。同じ問題を解決するための 10 の異なる方法が示されており、それぞれに独自のアプローチがあります。

さて、問題は、どれが最も優れているかをどのようにして知ることができるかということです。

私たちの目標は、時間と空間の複雑さを理解することです。これを行うために、2 つの異なるコード スニペットを使用した具体的な例を見てみましょう。そうすることで、これらの概念がどのように重要であるかを明確に理解できます。

これは addUpTo という関数です。この関数は、長さが n に達するまで実行される for ループを使用し、合計を返します。

次に、同じ機能を実現する別の例を見てみましょう。

どちらが良いでしょうか？

さて、この文脈において「より良い」とは実際には何を意味するのでしょうか?

• 速いですか?

• メモリ使用量は少なくなりますか?

• 読みやすくなりましたか?

通常、読みやすさを考慮する前に、最初の 2 つである速度とメモリ使用量に注目します。この場合、最初の 2 つに焦点を当てます。両方のコード例のパフォーマンスを測定するために、JavaScript の組み込みタイミング関数を使用して実行時間を分析し、比較します。

上記のコードでは、JavaScript に組み込まれている Performance.now() 関数を利用する t1 と t2 を追加しました。この関数は、コードの実行にかかる時間を測定するのに役立ち、2 つのアプローチのパフォーマンスを正確に比較できます。

まさに、実行時間はさまざまな要因によって異なります。私のコンピュータでもそれがわかります。時間は一定ではありません。 Performance.now() 関数は固定時間を示しませんが、比較に役立つ推定値を提供します。

次に、2 番目の例を見てみましょう:

次に、最初のコード例と 2 番目のコード例の実行時間の違いを観察してください。 2 番目は最初のものよりも明らかに高速です。

しかし、時間の測定だけに依存することには何が問題があるのでしょうか?

• マシンが異なれば記録される時間も異なります。

• 同じマシンであっても、実行ごとに異なるタイムを記録します。

• 非常に高速なアルゴリズムの場合、速度測定は正確な比較を行うほど正確ではない可能性があります。

これらの要因により、特に高速アルゴリズムの場合、時間ベースのパフォーマンス評価の信頼性が低くなります。

分かった、時間がないならどうする?

そこで、Big O が時間計算量と空間の両方を測定するのに役立ちます。つまり、Big O Notation はファジーカウントを形式化する方法です。これにより、入力が増加するにつれてアルゴリズムの実行時間がどのように増加するかについて正式に話すことができます。

コンピューターが実行しなければならない単純な演算の数が、n が増加するにつれて最終的に f(n) の定数倍よりも少なくなる場合、アルゴリズムは O(f(n)) であると言います。

• f(n) は線形である可能性があります (f(n) = n)

• f(n) は二次関数 (f(n) = n2) である可能性があります

• f(n) は定数になる可能性があります (f(n) = 1)

• f(n) はまったく異なるものになる可能性があります!

これが例です:

この場合、操作は 3 つだけであり、入力のサイズに関係なく、常に 3 つの操作のままです。このため、この関数の時間計算量は一定、つまり O(1).

であると言えるのです。

これが最初の例です:

この場合、入力 n が増加すると、演算数も比例して増加します。したがって、時間計算量は入力のサイズに依存し、O(n).

になります。

それでは、別の例を見てみましょう:

この例には 2 つの入れ子になった for ループがあり、両方とも n (入力) に依存します。これは、入力 n が増加すると、演算数が大幅に増加することを意味します。結果として、このコードの時間計算量は O(n²) となり、二次時間計算量とも呼ばれます。

さて、Big O 記法 を簡略化してみましょう。アルゴリズムの時間計算量を決定する際には、覚えておくと役立つ経験則がいくつかあります。これらのガイドラインは、Big O 表記の正式な定義から生じており、アルゴリズムの分析を容易にします。

定数は関係ない

• O(2n) = O(n)

• O(500) = O(1)

• O(13n²) = O(n²)

• O(n 10) = O(n)

• O(1000n 500) = O(n)

• O(n² 5n 8) = O(n²)

ビッグオーの略記

1. 算術演算は定数です

2. 変数の代入は定数です

3. 配列 (インデックスによる) またはオブジェクト (キーによる) の要素へのアクセスは定数です

4. ループ内の複雑さは、ループの長さとループ内で発生するあらゆるものの複雑さの積です

これが Big O チャートです:

これまでの例では、O(n) (線形時間計算量)、O(1) (一定時間計算量)、および について学習しました。 >O(n²) (二次時間計算量)。これらは、入力サイズに応じて操作が増大する基本パターンをカバーします。

O(log n) と O(n log n) (対数時間計算量と線形時間計算量) については後ほど説明します。

空間の複雑さ

これまで、時間計算量に焦点を当ててきました。入力のサイズが増加するにつれて、アルゴリズムの実行時間をどのように分析できるでしょうか?

ビッグ O 表記法を使用して空間の複雑さを分析することもできます。アルゴリズムでコードを実行するには、どのくらいの追加メモリを割り当てる必要がありますか?

入力はどうですか?

補助空間複雑度という用語は、入力によって占められる空間を含まず、アルゴリズムに必要な空間を指す場合があります。特に明記されていない限り、空間の複雑さについて話すときは、技術的には補助空間の複雑さについて話します。

JS の空間の複雑さ

• ほとんどのプリミティブ (ブール値、数値、未定義、null) は定数空間です

• 文字列には O(n) スペースが必要です (n は文字列の長さです) 参照型は通常 O(n) で、n は長さ (配列の場合) またはキーの数 (オブジェクトの場合)

覚えておいてください、私たちは時間の複雑さではなく、空間の複雑さについて話しているのです。このコードでは、変数が 2 つだけであることがわかります。入力がどれほど大きくなっても、これら 2 つの変数はコード内に常に存在します。入力が増加しても新しい変数を追加しないので、空間複雑度は O(1) であると言えます。これは、空間複雑度が一定であることを意味します。

別の例で理解してみましょう:

このコードでは、関数は入力配列内のすべての要素を 2 倍にした後、newArr を返します。 newArr のサイズは入力 arr のサイズに直接比例するため、newArr によって使用されるスペースは入力サイズとともに増加します。空間が一定だった前の例とは異なり、ここでは空間の複雑さは入力配列のサイズに依存します。したがって、空間複雑度は O(n) であり、線形であることを意味します。

これにより、空間の複雑さがより明確になることを願っています。時間の複雑さと同様に、私たちは Big O 表記法を使用して空間の複雑さを測定しています。これまで、さまざまな時間計算量について、複雑さの順に学習してきました: O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(n³) など。ただし、対数時間計算量についてはまだ調査していません。

次に、対数時間計算量を詳しく見て、それがどのように機能するかを確認します。

対数

最も一般的な複雑さのいくつかに遭遇しました: O(1)、O(n)、O(n2)。ビッグ O 式には、より複雑な数式が含まれる場合があります。思った以上に頻繁に登場するのは対数です!

ログとは何ですか?

log2 (8) = 3 → 2³ = 8

log2 (値) = 指数 → 2^指数 = 値

2 は省略します。つまり、次のことを意味します。

ログ === log2

数値の対数は、その数値が 1 以下になるまでにその数値を 2 で何回割ることができるかを大まかに測定します。これにより、対数時間計算量が非常に効率的になります。グラフで見たように、O(1) (定数時間) は O(log n) に非常に近く、これは素晴らしいことです。 O(n log n) は効率の点で O(n²) よりもはるかに優れており、多くのアルゴリズムにとって推奨される複雑さであることも注目に値します。

• 特定の検索アルゴリズムは対数的な時間計算量を持ちます。

• 効率的な並べ替えアルゴリズムには対数が含まれます。

• 再帰には対数空間の複雑さが含まれる場合があります。

すごいですね！空間と時間の複雑さに関する重要なポイントのほとんどをカバーしました。これらの概念を習得するには練習が必要なので、すぐに完全に理解できなくても圧倒されないでください。時間をかけて資料を何度も見直し、必要に応じて例を再確認してください。これらのアイデアを実際に理解するには、何度か繰り返す必要があることが多いので、辛抱強く待ってください!

最後に、もう一度おさらいしてみましょう:

• アルゴリズムのパフォーマンスを分析するには、Big O Notation を使用します

• Big O Notation を使用すると、アルゴリズムの時間または空間の複雑さを高度に理解できます

• Big O Notation は精度を考慮せず、一般的な傾向 (線形?二次?定数?) のみを考慮します

繰り返しになりますが、Big O Notation はどこにでもあるので、たくさん練習してください!

---

私たち CreoWis は、開発者コミュニティの成長を支援するために知識を公的に共有することを信じています。協力し、アイデアを出し、情熱を持って作り上げ、畏敬の念を抱かせる製品体験を世界に届けましょう。

接続しましょう:

• X/ツイッター

• LinkedIn

• ウェブサイト

この記事は、CreoWis の情熱的な開発者である Syket Bhattachergee によって作成されました。 X/Twitter、LinkedIn、 で彼に連絡したり、GitHub で彼の仕事をフォローしたりできます。 >

以上がBig O 記法を理解する: 時間と空間の複雑さに関する初心者向けガイドの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。