アルゴリズムの大きなオーバーヘッドと時間の複雑さ

アルゴリズム#アルゴリズム#

Big-O記号

Big−Oで測定した複雑さには時間と空間的複雑さがある.

時間の複雑さ

1             O(1)   --> 상수
2n + 20       O(n)   --> n이 가장 큰영향을 미친다.
3n^2          O(n^2) --> n^2이 가장 큰영향을 미친다.

O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N)번만큼의 수행시간을 가진다.(선형로그형)
O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.

Bubble Sort

export const ascending = arr => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - (i + 1); j++) {
      if (arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
      }
    }
  }
  return arr;
};

Heap Sort

const heapify = (arr, lastIdx) => {
  let idx = parseInt(lastIdx / 2) - 1;

  while (idx >= 0 ) {
    const left = arr[idx * 2 + 1];
    const right = arr[idx * 2 + 2];

    if (left >= right && arr[idx] < left) {
      const temp = arr[idx];
      arr[idx] = arr[idx * 2 + 1];
      arr[idx * 2 + 1] = temp;
    } else if (right > left && arr[idx] < right) {
      const temp = arr[idx];
      arr[idx] = arr[idx * 2 + 2];
      arr[idx * 2 + 2] = temp;
    }
    idx--;
  };
  return arr;
};

export const heapAscending = arr => {
  for(let i = arr.length - 1; i >= 0; i--) {
    arr = heapify(arr, i);

    if (arr[0] > arr[i]) {
      const temp = arr[i];
      arr[i] = arr[0];
      arr[0] = temp;
    }
  };
  return arr;
};

Merge Sort

const mergeSort = (array) => {
  if (array.length < 2) {
    return array;
  }

  const mid = Math.floor(array.length / 2);
  const left = array.slice(0, mid);
  const right = array.slice(mid);
  return merge(mergeSort(left), mergeSort(right));

  function merge(left, right) {
    const result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
      if (left[leftIndex] < right[rightIndex]) {
        result.push(left[leftIndex]);
        leftIndex++;
      } else {
        result.push(right[rightIndex]);
        rightIndex++;
      }
    }
    return result.concat(left.slice(leftIndex), right.slice(rightIndex));
  }
};

参照。