비효율적 연산과 Big O 표기법

Big O 표기법

성능 평가를 표현하기 위한 수학적 표기법으로 입력값에 따라 알고리즘이 수행되는데 얼마만큼의 시간이 걸리는가? 를 나타낸다. 최악의 경우를 예측하기 위한 방법으로 활용되기도 한다.

• 상수-시간: O(1) 입력 크기에 상관없이 동일한 시간이 걸리는 작업
• 선형-시간: O(n) 입력 크기에 비례하게 시간이 걸리는 작업
• 2차-시간: O(n^2) 중첩 반복문처럼 입력 크기에 제곱의 시간이 걸리는 작업
• 로그-시간: O(n log n) 퀵정렬, 병합정렬 등의 알고리즘과 같은 작업

상수 시간 알고리즘

const first = (array) => array[0];

const a = first([1,2]);
const b = first([1,2,3,4,5,6]);

first() 함수는 배열의 크기가 얼마가 됐든 상관없이 동일한 시간 복잡도를 가진다.

선형 시간 알고리즘

const findIndex = (array, value) => {
  for ( let i = 0, ilen = items.length; i < ilen; i++ )
    if (items[i] === value) return i;
  return -1;
};

const array = [1, 2, 3, 4, 5, 6, 7, 8];
findIndex(array, 1); // 첫번째에 반환 - 제일 좋은 경우
findIndex(array, 8); // 8번 반복 후 반환 - 최악의 경우
findIndex(array, 9); // 8번 반복 후 반환 - 최악의 경우

배열의 요소를 순차적으로 찾는 findIndex() 함수는 크기에 따라서 최악의 경우가 선형적으로 증가한다.

2차 시간 알고리즘

const makeMatrix = (row) => {
  const matrix = [];

  for ( let i = 0, ilen = row.length; i < ilen; i++ ) {
    matrix[i] = [];

    for ( let j = 0, jlen = row.length; j < jlen; j++ ) {
      matrix[i].push(row[j])
    }
  }

  return matrix;
};

const matrix1 = makeMatrix([1,2,3,4]); // 4개의 입력을 중첩 for문으로 인해 4^2 번 반복
const matrix2 = makeMatrix([1,2,3,4,5,6,7,8]); // 8개의 입력을 중첩 for문으로 인해 8^2 번 반복

위에 작성한 makeMatrix() 함수는 입력받은 배열의 개수만큼 행렬을 만들어내는 함수이다. 인자의 개수 만큼의 중첩 반복문을 거쳐 행렬을 만들어내므로 입력값의 크기에 따라 제곱된 시간 복잡도를 가지게 된다.

로그 시간 알고리즘

const quickSort = (list) => {
  if (list.length <= 1) return list;

  const pivot = list[list.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < list.length - 1; i++) {
    if (list[i] < pivot) left.push(list[i]);
    else right.push(list[i]);
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

// 사용 예시
const array = [34, 7, 23, 32, 5, 62];
const sorted = quickSort(array); // [5, 7, 23, 32, 34, 62]

퀵 소트를 구현한 예제이다. n번의 반복과 log n 깊이의 재귀호출이 발생하기 때문에 *O(n log n)*의 시간 복잡도를 가지게 된다.