TIL 27. BigO Notation(BigO記号)

Big - O

bigoマーキング法はアルゴリズム性能を数学的にマーキングするマーキング法である.時間&空間の複雑さを予測できます.現在、ハードウェアのパフォーマンスが向上するにつれて、空間的複雑さがアルゴリズムのパフォーマンスに与える影響はますます小さくなっているため、大きな5つのマーキング法は主に時間的複雑さによるパフォーマンスを予測するために使用されています.大きなエラータグ法で表される時間複雑度は,タグアルゴリズムの実際の実行時間よりも,データやユーザ成長率に基づいてアルゴリズムの性能を予測することに重点を置いている.
測定アルゴリズムの実際の実行時間には多くの限界がある.まず,機器の性能によっては同じアルゴリズムでも異なる運転時間を測定するため,異なるアルゴリズムの性能を比較することは困難である.また,実行時間が短いアルゴリズム間で比較すると,差が小さすぎて測定が困難である.従って、大エラーフラグ法の時間複雑度計算は、実行時間を基準とせず、パラメータ値nの増加に基づいて実行回数増加率を予測する方法を採用する.

(1) O(1), constant time

function (n) {
  return (n + n+1)/2
} 

数字nが増加すると、操作回数が同じになるため、性能は変わらない.これらのアルゴリズムをO(1)の時間的複雑さと呼ぶ.

(2) O(n), linear time

// n까지 정수의 총합을 구하는 알고리즘
function(n){ 
  let count = 0
  for (i =0; i<=n i++){
    count+=i
  }
 return count
}

上記アルゴリズムnの数が大きいほどfor文の動作回数も比例して増加するので、O(n)アルゴリズムとは、入力データに比例して処理時間を増加または減少させるアルゴリズムである.

(3) O(n^2), quardratic time

founction(n){
  for (i=0; i<n; i++){
    for(j=0;j<n; j++){
      console.log(i+j)
    }
  }
}

上記のアルゴリズムは、n個のデータを受信すると、各データに対してn回のfor文を実行し、二重のfor文の形式で実行し、nが大きいほど処理時間が長くなり、nの二乗となる.従って増加率はO(n)より大きい.

(4) O(nm), quardratic time

founction(n,m){
  for (i=0; i<n; i++){
    for(j=0;j<m; j++){
      console.log(i+j)
    }
  }
}

n個のデータをそれぞれm回実行するアルゴリズムで,総実行回数はnとmの積である.このアルゴリズムをO(nm)アルゴリズムと呼ぶ.

(5) O(n^3), polynomial / cubic time

founction(n){
  for (i=0; i<n; i++){
    for(j=0;j<n; j++){
      for(k=0;k<n; k++){
      console.log(i+j+k)
      }
    }
  }
}

上記のアルゴリズムは、n個のデータに3回乗じた回数に等しい3重for文で実行される.O(n^3)アルゴリズムの処理時間成長率はO(n^2)よりも速い.

(6) O(2^n), exponential time

O(2^n)の代表的アルゴリズムにはフィボナッチ数列がある.

function fibonacci(n){
  if (n < 2){
    retrun n
  }
  return fibonacci(n-1) + fibonacci(n-2)
}

関数が呼び出されるたびに2回呼び出され,アルゴリズムの実行回数は2^n回である.O(n^3)またはO(n^2)に比べて,データ成長による処理時間成長率が高かった.

(7) O(log n)

O(logn)の代表的アルゴリズムはバイナリ探索である.バイナリ検索は、実行するたびに中間値より前の要素が破棄されるため、シーケンス検索に比べて処理時間の増加率が低い.従って,O(n)と比較して,O(logn)アルゴリズムの処理時間成長率は低い.O(logn)アルゴリズムは,データ増加時の処理時間の性能に大きな変化はなかった.

定数を捨てる。

fuction (n){
  for(i=0; i<n; i++){
    console.log(n)
  }
  for(i=0; i<n; i++){
    console.log(n)
  }
}

上記の関数の動作回数は2 n回であるが,Oマーキング法ではO(2 n)ではなくO(n)と表記する.大きなエラーマーキング法は,実際のアルゴリズムの実行時間を測定するためではなく,データ対比処理時間の成長率を予測するためである.定数は固定値であり,定数を1つ増やすたびに固定定数に影響するのでbigoマーキング法では考慮しない.