データ構造とアルゴリズムにおける大きいO記法

計算機科学において,システム性能を解析するためのメトリックo表記法を述べた.これは、入力サイズの増加として関数やコードブロックの実行時間を測定するので、代数的な用語を使用してアルゴリズムの複雑さを決定します.
この概念はPaul Bachmann,Edund Landauらによって発明されたように漸近的表記法に特有であり,集合的にはBachmann - Landau表記法や漸近表記法と呼ばれている.

算術記法は上に示されるように、コンピュータアルゴリズムの全体的な複雑さを記述するいくつかの漸近的表記法が存在する.
Big O :以前に述べたように、複雑さがもう一つの機能、結果、または最悪の場合に「複雑でないか等しい」かどうかについて説明する機能制限を与えます.
ビッグ-Ω(ビッグオメガ):これは、関数が他より大きいか等しいかの境界を提供します.これは、“少なくとも”最高のケースであることが複雑さを与える.
ビッグ-θ(ビッグシータ):この非対称な表記法は、最悪と最高のケースの間の複雑さを与える.

アルゴリズムの複雑さは、アルゴリズムがサイズnの与えられた入力を完了するためにどのくらいの時間とどのくらいのメモリ空間が必要であるかの尺度です.

アルゴリズム

の時間複雑性

これは、アルゴリズムがその完了まで実行するのに要する合計時間を意味します.時間複雑さは、実行を終えるためにどんなアルゴリズムによっても実行される基本的なステップの数を数えることによって、最も一般的に見積もられます.異なる実行時の複雑さがあります.

O ( 1 ) -一定時間の複雑さ:
ここで、どんな与えられた入力のためのランタイムにも変化がありません.したがって、出力時間は一定値に依存し、入力サイズに依存しない.たとえば、配列内の任意の1つの要素にアクセスするには、1つの操作だけを実行する必要があります.

TimeComplex = [1,4,5,2,7,3]
TimeComplex[2] #accessing any element takes constant time

O ( n )-線形時間の複雑さ
入力のサイズが増加すると、実行時間は増加する.ゆえに、時間複雑度は入力データのサイズに直接比例する.それは、配列要素を通してループを必要とするアルゴリズムにおいて、または、アルゴリズムがその全体の入力をシーケンシャルに読まなければならないところに適している.たとえば、リストのすべての要素を追加する関数は、リストの長さに比例した時間を必要とします.

TimeComplex = [1,4,5,2,7,3]
for i in TimeComplex:
    print(i)

O ( n ^ 2 )[ OH n乗] 2次時間の複雑さ
これは、実行時のパフォーマンスがその入力データの四角形サイズに直接比例するアルゴリズムを表します.一般的な例は、配列内のすべてのインデックスを2回攻撃する入れ子になったループです.

TimeComplex = [1,4,5,2,7,3]
for i in TimeComplex:
    for j in TimeComplex:
        print(i)

O ( logn )-対数時間の複雑さ
これは、実行時のパフォーマンスが入力データサイズの対数に比例するアルゴリズムを表します.これは、特定のフィールドを検索するために数値のセットを半分に割り、その入力のすべての要素にアクセスする必要はありません.対数時間をとるアルゴリズムは、バイナリツリー上での演算やバイナリ検索を使用する場合に一般的に見られる.

TimeComplex = [1,4,5,2,7,3]
for i in range(1,len(TimeComplex),4):
        print(TimeComplex[i])

O ( 2 ^ n )-指数関数的時間複雑度
それらは、入力成長率が入力(n)に対する各々の加算で倍増するBurute Forceアルゴリズムと呼ばれていて、入力要素の全てのサブセットをしばしば繰り返す.
これは明らかにタスクを実行するのに最適な方法ではありません.彼らがシステムをアンロックする正しいパスワードを見つけるまで、ランダムなストリングを試みることによってパスワード保護を打ち破る方法を攻撃して、ブルートフォースアルゴリズムは暗号で使われます.

アルゴリズムの空間複雑度
空間複雑さはアルゴリズムによって必要とされる働く記憶の量です.そして、それを実行して、生じるためにアルゴリズム(アルゴリズムへの入力値を含む)によって使用されるメモリについて説明します.
これは、時間の複雑さに並列の概念であり、どのようにストレージのサイズを入力入力として成長を決定します.アルゴリズムの空間計算量を計算するためには,データ空間のみを考慮する.データ空間は、変数と定数によって使用されるスペースの量を参照します.

時間複雑性のような空間複雑さは、アルゴリズム/プログラムの効率を決定する際に重要な役割を果たす.アルゴリズムが多くの時間を取るならば、あなたはまだ待つことができます.しかし、プログラムが多くのメモリ空間を占有するなら、コンパイラはあなたにそれを走らせません.