ビオ記号法

の代表的な漸近標識法の一つ

最悪の場合、

アルゴリズムの複雑さは

である.

時間とアルゴリズム空間複雑度分析
漸近マーキング法とは?
整数論と解釈学の方法で,ある関数の増分を別の関数との比較として表す.
アルゴリズムの性能と効率をテストするために漸近マーキング法を用いた.
代表的なのは、大文字Oマーク法、大文字ωマーク法、大文字三ダースマーク法、小文字Oマーク法、小文字ωマーク法です

bigoマーキング法において、nは入力個数

を表す.
▲一般的なBIO複雑度

典型的な例

O(1)は入力空間を一定に保つ상수 시간と呼ばれています
たとえば、インデックスを使用して配列内のアイテムにアクセスします.O(n)は선형 시간であり、最悪の場合はn回の演算を実行する必要があるアルゴリズムに適用される
線形
直線のようにまっすぐな図形、あるいは類似の性質を持つオブジェクトを指し、このような性質を持つ変換などを表す用語である
関数の場合、どの関数の形状も「直線」として表示されます.
たとえば、数値列の合計を入力する順序を計算するには、数値列の長さに比例する時間が必要です.

O(n)アルゴリズムの例

function exampleLinear(n) {
  for (let i = 0; i < n; ++i) {
    console.log(i);
  }
}

exampleLinear(10);

// 출력결과
0
1
2
3
4
5
6
7
8
9

同様に、O(n²)は2回目の時間であり、O(n³)は3回目の時間である
二次時間と三次時間の複雑さの例は以下の通りである.

// 2차 시간 복잡도
function exampleQuadratic(n) {
  for (let i = 0; i < n; ++i) {
    console.log(i);
    for (let j = i; j < n; ++j) {
      console.log(j);
    }
  }
}

// 3차 시간 복잡도
function exampleCubic(n) {
  for (let i = 0; i < n; ++i) {
    console.log(i);
    for (let j = i; j < n; ++j) {
      console.log(j);
      for (let k = j; k < n; ++k) {
        console.log(k);
      }
    }
  }
}

ログ時間の複雑さを持つアルゴリズムの例は、次のとおりです.
2の2勝からn勝までの種目出力の場合

function exampleLogarithmic(n) {
  for (let i = 2; i <= n; i = i * 2) {
    console.log(i);
  }
}

exampleLogarithmic(1000000);

// 출력 결과
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288

ご覧のように、ログ時間の複雑さの効率と
大きな入力がある場合は、はっきりと表示されます
n 200万でもlog 100000は19.9315686なので19項目しか出力しません

ビオ記号規則

係数法則

合法則

乗子法則

転移法則

複数の法則

係数法則けいすうほうそく:除去定数さくじょていすう

カウント法則は,入力サイズに関係のない定数を単純に無視することである.
vigoでは、入力サイズが大きい場合、係数を無視できます.
f(n)がO(g(n)の場合、定数k>0となる.
kf(n)はO(g(n)である.
5 f(n)とf(n)が同じO(f(n)を持つbigo表記法

function a(n) {
  let count = 0;
  for (let i = 0; i < 5 * n; ++i) {
    count += 1;
  }
  return count;
}

console.log(a(10)); // 50

上のコードはf(n)=5 nです
0から5 nまで動作するからです.
しかし、これはO(n)の時間的複雑さを有する.
nが無限大または非常に大きい数に近づくと、演算が余分に存在しても変化しないからである.
nが十分大きい場合,上記のコードはn回実行されるといえる.
O(5 n)はO(n)と同様に線形成長したが,値は5倍に過ぎなかった.

合意法則:ヴィクトオを加える。

合意法則は時間の複雑さを増大させることを意味する
f(n)がO(h(n)、g(n)がO(p(n))である場合
f(n)+g(n)はO(h(n)+O(p(n))
このとき注意すべき点は,まず合意法則を適用し,次に係数法則を適用することである.

function a(n) {
  let count = 0;
  for (let i = 0; i < n; ++i) {
    count++;
  }
  for (let i = 0; i < 5 * n; ++i) {
    count++;
  }
  return count;
}

最初の繰り返し文はf(n)=nに相当する.
2番目の複文はf(n)=5 nに相当する
従って,結果値は6 nであったが,係数法則(除去定数)を適用し,最終結果はO(n)=nであった.

じょうほうそく

乗法はビオがどのように乗じたかについてです.
f(n)がO(h(n)、g(n)がO(p(n))である場合、
f(n)g(n)はO(h(n)p(n))

function a(n) {
  let count = 0;
  for (let i = 0; i < n; ++i) {
    count++;
    for (let i = 0; i < 5 * n; ++i) {
      count++;
    }
  }
  return count;
}

上記の例では、f(n)は5 n*nである
インナーループは5 n回、インナーループはn回運転するので
結果は5 n²反復演算
係数法則を適用した結果はO(n)=n²であった.

多恒の法則:比奥のk勝

複数の法則は,複数の時間複雑度が同じ複数の差を持つbigoマーキング法を意味する.
f(n)がk次多項式である場合、f(n)はO(n

function a(n) {
  let count = 0;
  for (let i = 0; i < n * n; ++i) {
    count++;
  }
  return count;
}

上記の例では、f(n)=n²はい.
簡単に言えば、比奥マーク法は最も影響力のあるものだけを気にすることを意味する.
(最高の車種を残して上司を捨てる)
値がO(30n³+20n²+500n+3000)と表示されると、
ビオマーク法は最も影響力のあるものだけを残し、O(n³)とマークされている.
この文章.📕参考JavaScriptで作成した資料構造とアルゴリズム書