漸近表記法(その1 )

プログラムを書くとき、最も効率的にコードが走るように、スマートプログラミング選択をすることは重要です.コンピュータはプログラムを評価するのに時間がかかりません.しかし、大量のデータを扱うためにプログラムをスケーリングするとき、効率的なコードを書くことは成功と失敗の違いになります.計算機科学では、プログラムが実行時にどの程度効率的であるかを定義する.
しかし、異なるコンピュータが異なる速度で動くので、我々はちょうどプログラムを間に合わせることができません.私のほこりっぽい古いPCは、あなたの真新しいラップトップと同じくらい速く走らない.プログラミングはまた、多くの異なる言語で行われます.これらの変数を横切ってプログラムの実行時を定義する一般的な方法が必要です.これを漸近表記で行う.
漸近表記法では、プログラムの入力の大きさに基づいてコンピュータが実行する命令数を見て、プログラムのランタイムを計算します.たとえば、コレクション内の最大要素を計算している場合は、コレクション内の各要素を検査する必要があります.使用する言語、または演算を実行しているCPUにかかわらず、その検査ステップは同じです.漸近表記法では、入力のサイズをnと定義します.n個の要素を100個の要素から探しているかもしれませんが、特定の数値の代わりにnが使用されるように、入力に対してどのように多くのステップを実行するかを知る必要があるだけです.第2の入力があるならば、我々はMとしてその入力のサイズを定義するかもしれません.
異なる懸念に焦点を絞った漸近表記の種類がある.いくつかのプログラムの最良のケースのシナリオを通信します.たとえば、コレクション内の値を検索している場合、最初の場所でその要素が見つかった場合に最適です.もう一つのタイプは、最悪のケース・シナリオに集中するでしょう、例えば、値を捜したなら、データセット全体を見て、それを見つけませんでした.通常、プログラマーは最悪の場合のシナリオに集中します.したがって、通信するためにランタイムの上限があります.それは“物事は悪い、または遅くなることがありますが、彼らはより悪くなることはありません”と言う方法です
この次のモジュールでは漸近的表記法,漸近表記法を通してプログラムの実行時を適切に解析する方法,プログラムを作成する際に異なるデータ構造とアルゴリズムの実行時間を考慮する方法についてより詳細に学習する.これらのスキルの学習は、プログラムを設計するときに考える方法を変更し、それは効率的なプログラムを作成するソフトウェア工学の世界のためにあなたを準備する重要なスキルです.

漸近表記とは何か

チーター.フェリス.ライフ.すべてが高速ですが、どのように最速の知っているのですか?あなたはスピードメーターでチーターとフェラーリの速度を測定することができます.あなたは人生と年と月を測定することができます.
しかし、コンピュータプログラムはどうですか?実際には、コンピュータプログラムをタイムアウトすることができますが、異なるコンピュータを別の速度で実行します.例えば、1つのコンピュータ上で12ナノ秒を取るプログラムは、他の上で45ミリ秒を取ることができました.したがって、プログラムのランタイムを測定するためのより一般的な方法が必要です.これを漸近表記で行う.
プログラムのタイミングの代わりに、漸近表記を通して、プログラムの入力の大きさに基づいて、コンピュータがどのように命令を実行するかを見ることによって、プログラムのランタイムを計算することができます.
例えば、サイズNの入力を有するプログラムは、コンピュータに5 N + 3 N + 2命令を走らせるように言うかもしれません.(今後の演習では、このような表現をどのように手に入れるのか)それにもかかわらず、これはまだかなり汚いと大規模な表現です.漸近記法については、Nが非常に大きくなるので、定数(数値)のすべてを削除します.定数は微小な違いを生じます.我々の定数を変更した後に、我々はN 2 + Nを持っています.

Image credits to Algorithms And Me
例えば、Nが1000であるとき:

N 2用語は、1000000

です

N項は、1000

です
ご覧のように、N 2用語はN項よりはるかに重要です.nが1000より大きい場合、その差はさらに大きくなる.違いがとても巨大であるので、ランタイムを計算するとき、我々はN項を考慮する必要さえありません.このプログラムのために、ランタイムをN 2で説明します.私たちはこのプログラムのランタイムを記述できる3つの異なる方法があります:ビッグシータまたはθ(N 2)、ビッグOまたはO(N 2)、ビッグオメガまたはΩ(N 2).

ビッグシータ

我々が探索する漸近表記の最初のサブタイプはビッグシータ(θで示される)です.プログラムが実行時に1つだけの場合、ビッグシータを使用します.しかし、それはどういう意味ですか?以下のリストに値を出力する関数の擬似コードを見てください.

Function with input that is a list of size N:
   For each value in list:
    Print the value

コンピュータが実行しなければならない命令の数は、ループがより多くの反復に基づいているので、ループがより反復を行う場合、コンピュータは命令を実行する.さて、ループがnの値にどのように繰り返されるかを見ましょう.
すべてのケースで見ることができるように、サイズNのリストで、プログラムはNの値を印刷しなければならないので、Nのランタイムを持ちます.したがって、ランタイムはθ( n )となります.
もっと複雑な例を見てみましょう.次の擬似コードプログラムでは、関数nをとり、nが1に達するまで、nを2で割る回数を数えます.

Function that has integer input N:
  Set a count variable to 0
  Loop while N is not equal to 1:
      Increment count
      N = N/2
  Return count

しかし、単一のプログラムのために複数のランタイムケースがあるとき、何が起こりますか?来週のパート2のための滞在曲!