big-oマーク法とは何ですか?

big−oマーキング法は、データまたはユーザの増加に伴うアルゴリズムの性能を予測するために、アルゴリズムの時間および空間的複雑さを数学的に表現するマーキング法である.正確な実際の処理時間を測定するのではなく,大まかな成長率を予測するので,成長率に一定の影響を及ぼす定数は敢えて捨てなければならない.
代表的な5つのスペルをまとめます.

O(1)

const n = [0,1,2,3,4];

function fn1(n) {
  return n[0] === 0 ? true : false;
}

上記のコードでは、nの長さ、値の大きさにかかわらず、fn関数はnの0番目のインデックスのみを検索してboolean結果値を返すため、処理時間はデータのサイズに関係ありません.
この場合,fn関数はO(1)の時間的複雑さを持つといえる.

O(n)

const n = [0,1,2,3,4];

function fn2(n) {
  for(let i = 0; i < n.length; i++) {
    console.log(n[i]);
  }
}

同じ論理でfn 2関数を見ると,nの長さが1つ増えるごとにfor文が1回返されるので,nの長さは処理時間に比例する.データ(x軸)と処理時間(y軸)の関係は、O(n)の時間的複雑さを持つ上向きの直線を描画します.

O(n²)

const n = [0,1,2,3,4];

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

fn 3関数は[nの長さxnの長さ]をループ文とするので,nの長さに応じて処理時間はnの二乗で増加する.データ(x軸)と処理時間(y軸)の関係は傾斜曲線であり,O(n)である上向き曲線である²)時間の複雑さがあります.

O(nm)

const n = [0,1,2,3,4];
const m = [0,1,2];

function fn4(n) {
  for(let i = 0; i < n.length; i++) {
    for(let j = 0; j < m.length; j++) {
      console.log(i + j);
    }
  }
}

fn 4はfn 3に似ているが、内部のfor文は配列mの長さに戻る.fn 3とは異なり、mの長さはnよりも長くてもよいし、nよりも短くてもよいので、関数の処理時間ではnのほかにmも影響を受ける.図ではfn 3と同様に,勾配が増加した右上曲線を描いている.

O(n³)

const n = [0,1,2,3,4];

function fn5(n) {
  for(let i = 0; i < n.length; i++) {
    for(let j = 0; j < n.length; j++) {
      for(let k = 0; k < n.length; k++) {
        console.log(i + j + k);
      }
    }
  }
}

O(n²)理解すれば、fn 5の演算回数がnの長さxnの長さxnの長さ、すなわちnの立方晶であることを容易に受け入れることができる.nの長さが増すとO(n)²)これに対して、データ(x軸)と処理時間(y軸)のグラフは、傾斜がより急な右上曲線を示している.

O(2ⁿ)

// 피보나치 수열의 n번째 값을 반환하는 함수

function fn6(n) {
  if(n <= 1) {
    return n;
  } else {
    return fn6(n-2) + fn6(n-1)
  }
}

上の関数でnumの大きさが1大きくなると耳が2回回り、そのうち2回...その中でまた2回...演算は、逃走条件が満たされるまで2のn乗を返す.
nが20の場合、処理時間はO(n)³) 一方、O(2𔓼)では8000にすぎず、O(2𔓼)では10576とは異なる.データ(x軸)と処理時間(y軸)のパターンでは,曲線の傾きはO(n)である.³) これよりもっとひどいです.

O(log n)

//아래 함수는 이진탐색 로직을 구성하고 있다.

function fn7(target, n) {

  let start = 0;
  let end = n.length - 1;
  
  while (start <= end) {
    let middle = n[Math.floor((start + end) / 2)];
  
    if (middle === target) {
      return true;
    } else if (middle > target) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
  }
  
  return false;
}

バイナリ検索はO(logn)を表す代表的な関数といえ,up downゲームに似たデータ検索方法である.バイナリ検索は非常に効率的な検索方式であり、データ量がどんなに大きくても、処理時間は大きく異なります.
データの中間値をつかんで、もし私が検索する値が中間値より小さいならば、私は中間値より大きいデータをすべて捨てて、更に半分に分かれたデータの中から再び中間値を獲得して、もし私の目標値が中間値より大きいならば、私は中間値より小さいデータをすべて捨てて、再び中間値を獲得します...これはやることで目標を見つける方法です.バイナリ探索を習ったことがないので、何の話かよく知らない場合は、上記のサンプルコードを直接打ったほうがいいです.