Big-O-Notation(漸近線マーク)

Big-O-Notation

アルゴリズムの速度を表す方法

アルゴリズムの速度を秒単位で表すことはできません.同じコードを実行しても、ハードウェアによっては千差万別の速度差があるからです.したがって、タスクを実行するために必要なステップに基づいて速度を計算します.
Ex)5ステップ必要アルゴリズムは10ステップ必要アルゴリズムより効率が高い

コードの実際の実行時間は表示されず、入力データの増加率に伴うアルゴリズムのパフォーマンスの変化を予測するために使用されます.

実際の実行時間を表示しない理由は,アルゴリズムが4 n+9時間,nが10億であると仮定すると,このアルゴリズムの実行に40億+9時間かかるとは誰も言わないからである.
したがって、Big-O-Notationでは、次のルールが使用されます.

1.最高の回数しか残っていない。

O(n² + n) -> O(n²)   

差のないnはアルゴリズムの実行時間にほとんど影響を及ぼさない

2.係数及び定数を果敢に廃棄する。

O(2n + 3) -> O(n)
O(3N) ➡ O(N)
O(N² +2) ➡ O(N²)

同様に,係数および定数はアルゴリズムの実行時間に影響を及ぼさない.

例

一定時間

function getFirstItem(arr) {
  return arr[0];
}

上のコードは配列を受信し、最初の値を返します.この場合、アレイのサイズに関係なく、最初の値が無条件に返されるため、アレイのサイズに関係なく時間が決定されます.
したがって,上記関数の時間的複雑さを定数時間(定数時間)と呼ぶことができる.

一番下のO(1)は定数時間です.
上記のコードを次のように変更した場合:

function getFirstItem(arr) {
  console.log(arr[0]);
  console.log(arr[0]);
}

正解はNo!はい.前述したように、Big-Oはコードの詳細にあまり興味がありません.従って、実行時間が入力データの影響を受けない場合は、全てO(1)と表示される.
上記の一定時間に実行されるコードは常に人気があるが、実際には生成しにくいという問題がある.

リニアタイム

def printAll(arr):
 for n in arr:
  print(n)

以上のコードは配列を入力し、配列内のすべての項目を出力します.アレイのサイズが10の場合は10回、100の場合は100回出力されます.すなわち、この時間的複雑度をBig-Oと表記すると、以下のようになる.

O(n)線形時間複雑度
上記のアルゴリズムはいずれも入力の大きさと速度に比例する.

時間

回、合計

回

def print_twice(arr):
 for n in arr:
  for x in arr:
   print(x, n)

上記のコードは、アレイ内の各アイテムに対してループを繰り返します.したがって,時間的複雑さはn^2に変化し,10項目に100ステップが必要であることを意味する.

入力の大きさが大きいほど、時間は幾何級数で増加するので、あまり人気のないアルゴリズムです.

ログ時間
まずログを調べてみましょう.ログは指数と正反対です.したがって,下部2のログに32を入れると,2^5は32となるため,結果は5となる.このようにログを使用すると、入力よりもはるかに小さい値が生成され、次のグラフが表示されます.

上記のグラフから、ログ時間は線形時間に非常に近いことがわかります.従って,定数時間に次ぐ速度が最も速いアルゴリズムに属する.