ビッグシータと漸近表記の説明

Big Omegaは関数の実行時間の下限を示し、BigOは上限を示します。

多くの場合、それらは異なり、ランタイムを保証することはできません。これは、2つの境界と入力の間で異なります。しかし、それらが同じである場合はどうなりますか?次に、シータ(Θ)バウンドを与えることができます-どの入力を与えても、関数はその時間に実行されます。

一般に、シータ境界は最も正確で最もタイトな境界であるため、可能であれば常にシータ境界を指定する必要があります。シータバウンドを与えることができない場合、次善の策は可能な限り最もタイトなOバウンドです。

たとえば、配列で値0を検索する関数を考えてみましょう。

def containsZero(arr): #assume normal array of length n with no edge cases for num x in arr: if x == 0: return true return false
  1. 最良のケースは何ですか?さて、私たちが与える配列の最初の値が0の場合、一定の時間がかかります:Ω(1)
  2. 最悪の場合は何ですか?配列に0が含まれていない場合は、配列全体を反復処理します。O(n)

オメガとOバウンドを与えたので、シータはどうですか?あげられない!与える配列に応じて、実行時間は定数と線形の間のどこかになります。

コードを少し変更しましょう。

def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)

最良の場合と最悪の場合を考えられますか?できません!どの配列を指定しても、配列内のすべての値を反復処理する必要があります。したがって、この関数は少なくともn時間(Ω(n))かかりますが、n時間(O(n))より長くはかからないこともわかっています。これは何を意味するのでしょうか?私たちの関数は正確にn時間かかります:Θ(n)。

境界がわかりにくい場合は、次のように考えてください。xとyの2つの数があります。x <= yおよびy <= xが与えられます。xがy以下で、yがx以下の場合、xはyと等しくなければなりません。

リンクリストに精通している場合は、自分でテストして、これらの各関数のランタイムについて考えてください。

  1. 取得する
  2. 削除する
  3. 追加

二重にリンクされたリストを検討すると、事態はさらに興味深いものになります。

漸近表記

アルゴリズムのパフォーマンス値をどのように測定しますか?

時間は私たちの最も貴重なリソースの1つであると考えてください。コンピューティングでは、プロセスが完了するまでにかかる時間でパフォーマンスを測定できます。2つのアルゴリズムで処理されるデータが同じである場合、問題を解決するための最適な実装を決定できます。

これを行うには、アルゴリズムの数学的限界を定義します。これらは、big-O、big-omega、big-theta、またはアルゴリズムの漸近表記です。グラフでは、big-Oは、アルゴリズムが特定のデータセットに対して取ることができる最長の時間、つまり「上限」になります。Big-omegaは、big-Oの反対の「下限」のようなものです。ここで、アルゴリズムはどのデータセットでも最高速度に達します。ビッグシータは、アルゴリズムの正確なパフォーマンス値、または狭い上限と下限の間の有用な範囲のいずれかです。

いくつかの例:

  • 「配達はあなたの生涯の中でそこにあります。」(big-O、上限)
  • 「私はあなたに少なくとも1ドル支払うことができます。」(ビッグオメガ、下限)
  • 「今日の最高気温は25℃、最低気温は19℃になります。」(ビッグシータ、ナロー)
  • 「ビーチまでは徒歩1キロです。」(ビッグシータ、正確)

詳しくは:

//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% A8-notation-represent //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/