データ構造の大きな表記法：知っておくべきことすべて

データ構造のBigO表記は、アルゴリズムの効率、入力の増加に伴って関数を実行するのにかかる時間、および関数のスケーリングを決定するために使用されます。 この効率の測定は、空間の複雑さと時間の複雑さの2つの部分に分けることができます。

Big O表記は、引数が特定の値または無限大に傾く傾向がある場合に、関数の制限要因として機能する数学表記を指します。 これは、エドマンド・ランダウ、ポール・バッハマンなどによって発明された数学表記のカテゴリーに属しています。 したがって、これはまとめてバッハマン-ランダウ表記または漸近表記と呼ばれます。

数学的推論によると、2つの関数f（n）とg（n）は、バインドされていない正または実数のセットで定義されます。 ここで、 g（n）は、nのすべての大きな値に対して厳密に正です。 次のように書くことができます。

f（n）= O（g（n））ここで、nは無限大になる傾向があります（n→∞）

ただし、ここでは、nから無限大への仮定が排他的に定義されているわけではないため、上記の式は次のように記述できます。

f（n）= O（g（n））

ここで、fとgは、正の整数から非負ではない実数までの必要な関数です。

したがって、大きなn値は、BigO漸近線で表されます。

データ構造におけるBigO表記のプロパティ

データ構造のBigOアルゴリズムには、必須のプロパティがかなりあります。 Big O表記の前述の本質的な特性は、次のとおりです。

• 合計関数：
  f（n）= f 1 （n）+ f 2 （n）+ — + f m （n）およびf i （n）≤fi +1 （n）∀i= 1、2、–、m、
  次に、O（f（n））= O（max（f1（n）、f2（n）、–、fm（n）））。
• 対数関数：
  f（n）= loganおよびg（n）= logbnの場合、
  次にO（f（n））= O（g（n））
• 定数乗算：
  f（n）= cg（n）の場合、O（f（n））= O（g（n））ここで、cは非ゼロ定数です。
• 多項式関数：
  f（n）= a0 + a1.n + a2.n2 + — + am.nmの場合、
  次に、O（f（n））= O（nm）。

世界のトップ大学からオンラインでソフトウェア開発コースを学びましょう。 エグゼクティブPGプログラム、高度な証明書プログラム、または修士プログラムを取得して、キャリアを迅速に追跡します。

人気のソフトウェアエンジニアリングコースをご覧ください

ここでは、Big Oに対処している間、すべてのログ関数が同様に増加します。

アルゴリズムの実行時分析におけるBigO表記の重要性

アルゴリズムの最悪の場合の実行時間の複雑さは、特にアルゴリズムのパフォーマンスを分析する場合に、比較を描画して計算するために使用されます。 一定の実行時間として示されるO（1）の順序は、アルゴリズムの最速の実行時間です。アルゴリズムにかかる時間は、さまざまな入力サイズで同じです。 アルゴリズムの理想的な実行時間は一定の実行時間であることに注意することが重要です。これは、アルゴリズムの実行時間がnの入力サイズに依存するため、ほとんど達成されません。

例えば：

上記のように、アルゴリズムの実行時パフォーマンスは、nの入力サイズに大きく依存します。 さまざまなサイズのnのアルゴリズムの実行時分析を行うために、いくつかの数学的例を使用してこの事実を解明しましょう。

• n = 20
  ログ（20）= 2.996;
  20 = 20;
  20ログ（20）= 59.9;
  20 2 = 400;
  2 20 = 1084576;
  20！ = 2.432902 + 18 18 ;
• n = 10
  log（10）= 1;
  10 = 10;
  10ログ（10）= 10;
  10 2 = 100;
  2 10 = 1024;
  10！ = 3628800;

アルゴリズムの実行時パフォーマンスも同様に計算されます。

ランタイム分析の他のいくつかのアルゴリズムの例を次に示します–

• 線形検索に関しては、実行時の複雑さはO（n）です。
• 実行時の複雑さは、バイナリ検索の場合はO（log n）です。
• 選択ソート、バブルソート、バケットソート、挿入ソートの場合、実行時の複雑さはO（n ^ c）です。
• ハノイの塔などの指数アルゴリズムの場合、実行時の複雑さはO（c ^ n）です。
• マージSortSortおよびヒープソートの場合、実行時の複雑さはO（n log n）です。

Big Oはスペースの複雑さをどのように分析しますか？

アルゴリズムのスペースと実行時の複雑さの両方を決定することは、重要なステップです。 これは、アルゴリズムの実行時のパフォーマンスと、アルゴリズムのスペースの複雑さの分析を通じてアルゴリズムが使用しているメモリスペースを分析することで、アルゴリズムにかかる実行時間を決定できるためです。 したがって、アルゴリズムのスペースの複雑さを測定するには、アルゴリズムの最悪の場合のスペースの複雑さのパフォーマンスを比較する必要があります。

アルゴリズムのスペースの複雑さを判断するには、次の2つのタスクに従う必要があります–

タスク1：特定のアルゴリズム用のプログラムを実装することが重要です。

タスク2：各アイテムが保持するメモリを決定するには、入力nのサイズを知ることが不可欠です。

これらの2つの重要なタスクは、アルゴリズムのスペースの複雑さを計算する前に実行する必要があります。

空間複雑性アルゴリズムの例

スペースが複雑なアルゴリズムの例はたくさんありますが、このタイプのアルゴリズムをよりよく理解するために、その一部を以下に示します。

• バブルソート、線形検索、選択ソート、挿入ソート、ヒープソート、およびバイナリ検索の場合、スペースの複雑さはO（1）です。
• 基数ソートに関しては、スペースの複雑さはO（n + k）です。
• スペースの複雑さは、SortSortをすばやく実行するためにO（n）です。
• マージソートの場合、スペースの複雑さはO（log n）です。

CでのBigO表記の例

Big O表記は、アルゴリズムの複雑さやパフォーマンスを判断するために、主にコンピュータサイエンスで使用されているのは事実です。 この表記法により、入力データの範囲が大きくなった場合のメモリスペースの増加または実行時間の要件に基づいてアルゴリズムの動作を分類することができます。 これは、実際のメモリ使用量や実行時間を予測するようには設計されていませんが、アルゴリズムを比較し、その中からジョブに最適なものを選択するために設計されています。 言語固有ではありませんが、Cでも実装されています。

以下に、アルゴリズムの最悪の場合の複雑さ（Big O表記）が計算されたCの選択ソートアルゴリズムを示します。-

for（int i = 0; i <n; i ++）

{{

int min = i;

for（int j = i; j <n; j ++）

{{

if（array [j] <array [min]）

min = j;

}

int temp = array [i];

array [i] = array [min];

array [min] = temp;

}

アルゴリズムを分析するには：

• for外部ループの範囲がi<nであることはすでに示されています。これは、ループの順序がO（n）であることを示しています。
• 次に、内側のforループのj <nとしてO（n）でもあることを確認できます。
• 定数cの平均効率がn/2である場合でも、定数は無視されます。 したがって、順序はO（n）です。
• 内側のループと外側のループの順序を乗算した後、達成される実行時の複雑さはO（n ^ 2）です。

Cの他のアルゴリズムは簡単に実装でき、複雑さも同様に簡単に分析および決定できます。

BigO表記の使用法

BigO表記が適用される主な領域は2つあります。-

• 数学：Big O表記法は、数学の分野で非常に一般的に使用されており、特に漸近展開または切り捨てられたテイラー級数の場合に、有限級数が関数をどのように近似するかを説明します。
• コンピュータサイエンス： Big O表記は、アルゴリズムの分析に役立つため、コンピュータサイエンスの分野で主に使用されていることは十分に確立された事実です。

ただし、どちらのアプリケーションでも、 O （・）内に現れる関数g （ x ）は、低次の項と定数係数を省略した場合に、おそらく最も単純になるように選択されることがよくあります。

この表記法には、形式的には近いが比較的異なる2つの使用法があります。 彼らです：-

• 無限の漸近解析
• 微小な漸近解析。

ただし、この区別は原則としてではなく、「ビッグO」の正式な定義が両方の場合でまったく同じである場合にのみ適用されます。 唯一の違いは、関数の引数の制限です。

ソフトウェア開発に関連する人気の記事を読む

結論

結論として、ビッグデータはデータ構造において不可欠な役割を果たしていると言えます。ビッグO表記についての深く包括的な知識を持つことは、優れたスキルセットです。 それは仕事の分野で高い需要があり、キャリアパスのための潜在的に素晴らしい選択になる可能性があります。 ビッグデータにおけるupGradの高度な証明書プログラムは、あなたのキャリアを後押しするために必要なレバレッジを提供します。 PySparkを使用したデータ処理、データウェアハウジング、MapReduce、AWSクラウドでのビッグデータ処理、リアルタイム処理などの最高の専門スキルを紹介します。