時間複雑度(BigO)

これは、YouTubeエンジニアの時間的複雑さを紹介し、整理し、サンプルコードをJavaScriptまたは新編に変更したコメント記事です.

時間複雑度(BigO)

アルゴリズム性能を表す数学的表現

アルゴリズムの時間・空間的複雑さを表すことができる

アルゴリズムの実稼働時間と比較して、データまたはユーザ成長率に基づいてアルゴリズム性能を予測することを目標とする

なるOマーク法では、定数は果敢に切り捨てる!ex. O(2n) => O(n)
→原因:予測性能が目標だから.

📖 O(1)

:入力データのサイズにかかわらず、アルゴリズムには一定の時間がかかります.

const printFirst = (array) => console.log(array[0]);

📖 O(n)

:処理時間が入力データサイズに比例するアルゴリズム

const printNumbers = (array) => array.forEach((num) => console.log(num));

📖 O(n²)

:n個のデータを2回遍歴するアルゴリズム

function calculate(arr1) {
  let newArray = [];
  for (let i = 0; i < arr1.length; i++) {
    for (let j = 0; j < arr1.length; j++) {
      newArray.push(i + j);
    }
  }
}

📖 O(nm)

: O(n²)これとは異なり、n個のデータを2回回転するのではなく、m個のデータを回転させる.

function calculate(arr1, arr2) {
  let newArray = [];
  for (let i = 0; i < arr1.length; i++) {
    for (let j = 0; j < arr2.length; j++) {
      newArray.push(i + j);
    }
  }
}

📖 O(n³)

:n個のデータを3回遍歴するアルゴリズム(立方体形状)

function calculate(arr1) {
  let newArray = [];
  for (let i = 0; i < arr1.length; i++) {
    for (let j = 0; j < arr1.length; j++) {
      for (let k = 0; k < arr1.length; k++) {
        newArray.push(i + j + k);
      }
    }
  }
}

📖 O(2ⁿ)

:典型的な例-フィボナッチ数列

function fibonacci(n, r) {
  if (n <= 0) return 0;
  else if (n == 1) return (r[n] = 1);
  return (r[n] = fibonacci(n - 1, r) + fibonacci(n - 2, r));
}

📖 O(log n)

:処理するたびに取得するデータを半減するアルゴリズム
:典型的な例-バイナリ検索
バイナリサーチ
:昇順でソートされたリストで特定の値の位置を検索するアルゴリズム.
初期中間値を任意の値として選択することで、その値と検索する値のサイズを比較します.

function binarySearch(key, array, start, end) {
  if (start > end) return -1;
  mid = (start + end) / 2;
  if (arr[mid] == k) return mid;
  else if (arr[mid] > k) return binarySearch(key, array, start, mid - 1);
  else return binarySearch(key, array, mid + 1, end);
}

📖 O(sqrt(n))

平方根

リファレンス

油管技師大韓民国:https://www.youtube.com/watch?v=6Iq5iMCVsXA

(フィボナッチ数列関連):https://swtpumpkin.github.io/algorithm/level1/fibonacciNumber/