4장 빅 오로 코드 속도 올리기

김현수·2022년 2월 7일

누구나 자료 구조와 알고리즘 알고리즘

누구나 자료 구조와 알고리즘

목록 보기

4/20

빅 오를 사용하면 내가 만든 알고리즘과 세상에 존재하는 범용 알고리즘을 비교할 수 있다.

4.1 버블 정렬

정렬 알고리즘: "정렬되지 않은 배열이 주어졌을 때, 어떻게 오름차순으로 정렬할 수 있을까?"

버블 정렬의 단계

배열 내에서 연속된 두 항목을 가리킨다. 처음에는 배열의 첫 번째부터 두 항목을 가리킨다. 첫 번째 항목과 두 번째 항목을 비교한다.
두 항목의 순서가 뒤바뀌어 있으면 두 항목을 교환한다. 순서가 올바르다면 2단계에서는 아무것도 하지 않는다.
포인터를 오른쪽으로 한 셀씩 옮긴다.
배열의 끝까지 또는 이미 정렬된 값까지 1-3단계를 반복한다. 이것을 "배열의 패스스루가 끝났다"라고 표현한다.
두 포인터를 다시 배열의 처음 두 값으로 옮겨서 1-4단계를 실행해 새로운 패스스루를 실행한다. 교환이 일어나지 않는 패스스루가 생길 때까지 패스스루를 반복한다. 교환할 항목이 없다는 것은 배열이 정렬됐고 문제를 해결했다는 뜻이다.

4.2 버블 정렬 실제로 해보기

[4, 2, 7, 1, 3]을 오름차순으로 버블 정렬한다고 가정한다.

4, 2를 비교한다.
순서가 맞지 않으므로 둘을 교환한다. [2, 4, 7, 1, 3]
다음으로 4, 7을 비교한다. 순서가 올바르므로 교환할 필요가 없다. [2, 4, 7, 1, 3]
7, 1을 비교한다.
순서가 맞지 않으므로 둘을 교환한다. [2, 4, 1, 7, 3]
7, 3을 비교한다.
순서가 맞지 않으므로 둘을 교환한다. [2, 4, 1, 3, 7]
이제 7은 확실히 배열 내에서 올바른 위치에 있다. 7은 정렬되지 않은 값 중 가장 큰 값, 즉 '버블'이었고, 계속해서 오른쪽으로 옮겼기 때문이다.

첫 번째 패스스루에서 한 번 이상의 교환을 수행했으므로 다음 패스스루를 진행한다.
2, 4를 비교한다. 순서가 올바르므로 교환할 필요가 없다. [2, 4, 1, 3, 7]
4, 1을 비교한다.
순서가 맞지 않으므로 둘을 교환한다. [2, 1, 4, 3, 7]
4, 3을 비교한다.
순서가 맞지 않으므로 둘을 교환한다. [2, 1, 3, 4, 7]
첫 번째 패스스루를 통해 7이 이미 올바른 위치라는 것을 알고 있으니 4와 7은 비교할 필요가 없다. 두 번째 패스스루가 끝났다.

두 번째 패스스루에서 한 번 이상의 교환을 수행했으므로 다음 패스스루를 진행한다.
2, 1을 비교한다.
순서가 맞지 않으므로 둘을 교환한다. [1, 2, 3, 4, 7]
2, 3을 비교한다. 순서가 올바르므로 교환할 필요가 없다. [1, 2, 3, 4, 7]
3이 올바른 위치로 올라갔다. 세 번째 패스스루가 끝났다.

두 번째 패스스루에서 한 번 이상의 교환을 수행했으므로 다음 패스스루를 진행한다.
1, 2를 비교한다. 순서가 올바르므로 교환할 필요가 없다.
나머지 값은 모두 이미 올바르게 정렬됐으므로 네 번째 패스스루가 끝났다.
교환을 수행하지 않았으므로 배열이 완전히 정렬됐다. [1, 2, 3, 4, 7]

4.2.1 버블 정렬 구현

const bubbleSort = (list) => {
  let unsortedUntilIndex = list.length - 1;
  let sorted = false;
  while (!sorted) {
    sorted = true;
    for (let i = 0; i < unsortedUntilIndex; i++) {
      if (list[i] > list[i + 1]) {
        [list[i], list[i + 1]] = [list[i + 1], list[i]];
        sorted = false;
      }
    }
    unsortedUntilIndex -= 1;
  }
  return list;
};

unsortedUntilIndex 변수는 아직 정렬되지 않은 배열의 가장 오른쪽 인덱스이다. 초깃값은 배열의 마지막 인덱스이다.

sorted 변수는 정렬되어 있는지를 나타낸다.

while 루프는 패스스루에 해당한다. 한 번의 루프가 한 번의 패스스루이다. 각 패스스루는 정렬이 되어 있다고 가정하고 값을 교환하면 sorted 변수를 false로 바꾼다. 따라서 교환이 일어나지 않는다면 sorted 변수가 true로 남아서 배열이 정렬된 상태임을 알 수 있다.

for 루프는 배열 내 모든 값 쌍을 가리키며 배열의 첫 인덱스부터 정렬되지 않은 인덱스(unsortedUntilIndex)까지 반복문을 실행한다. for 루프 내에서 모든 인접 값 쌍을 비교하고 순서가 맞지 않으면 교환한다. 그리고 sorted 변수를 false로 바꾼다.

각 패스스루가 끝나면 unsortedUntilIndex의 값이 정렬된 상태이니 1을 감소시킨다.

sorted가 true가 되면 while 루프가 종료되고 정렬된 배열을 반환한다.

4.3 버블 정렬의 효율성

버블 정렬 알고리즘은 1) 비교, 2) 교환이라는 중요한 단계를 포함한다.

4.2의 예시인 원소 5개의 배열에서 첫 번째 패스스루는 4번, 두 번째는 3번, 세 번째는 2번, 네 번째는 1번의 비교를 했다.
즉, 버블 정렬은 (N-1) + (N-2) + (N-3) + ... + 1번의 비교를 수행한다.

최악의 시나리오라면 버블 정렬은 비교할 때마다 교환을 해야 한다. 4.2의 예시처럼 원소가 5개라면 비교가 10번 일어났으므로 교환도 10번 일어난다.

즉, 최악의 시나리오에선 정렬까지 총 20단계가 필요하다.

원소 10개 배열의 최악의 시나리오에선 45 + 45 = 90단계가 필요하다.
원소 20개 배열의 최악의 시나리오에선 190 + 190 = 380단계가 필요하다.

즉, 버블 정렬은 원소가 N개일 때 대략 N²만큼 늘어난다. 따라서 빅 오로 나타내면 버블 정렬의 효율성은 O(N²)이다. 이를 이차 시간이라고도 부른다.

O(N²)은 데이터가 증가할 때 단계 수가 급격히 늘어나므로 비교적 비효율적인 알고리즘으로 간주된다.

4.4 이차 문제

배열에 중복 숫자가 있는지 확인할 때, 가장 먼저 떠오르는 방법 중 하나는 중첩 루프이다.

const hasDuplicateValue = (array) => {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; i++) {
      if (i !== j && array[i] === array[j]) {
        return true;
      }
    }
  }
  return false;
};

확인할 배열에 중복값이 없는 것이 최악의 시나리오다. 이때 바깥 루프는 배열을 전부 살펴보기 위해 N번을 순회해야 하고, 순회할 때마다 안쪽 루프는 다시 N번을 순회해야 한다. 즉, O(N²)인 알고리즘이다.

루프 내에 다른 루프를 중첩하는 알고리즘이라면 대부분 O(N²)이다. (항상은 아니다) O(N²)은 상대적으로 느린 알고리즘으로 간주되기에, 시간을 들여 더 빠른 대안은 없을지 깊이 생각해 보는 것이 좋다.

4.5 선형 해결법

다음처럼 중첩 루프를 쓰지 않는 hasDuplicateValue 함수를 구현해 볼 수 있다.

const hasDuplicateValue = (array) => {
  const existingNumber = [];
  for (let i = 0; i < array.length; i++) {
    if (existingNumber[array[i]] === 1) {
      return true;
    } else {
      existingNumber[array[i]] = 1;
    }
  }
  return false;
};

existingNumber라는 빈 배열을 생성하고, 반복문을 시작한다.

반복문에선 배열의 원소 값을 existingNumber의 인덱스로 하여 해당 인덱스에 임의의 값(예제에서는 1)을 집어넣는다. 이때, 조건식으로 해당 인덱스에 이미 1이 있는지 확인하여, 없다면 집어넣고, 있다면 중복 값이 있다는 뜻이므로 true를 리턴한다. true가 반환되지 않고 반복문이 끝났다면 중복 값이 없다는 뜻이므로 false를 반환한다.

hasDuplicateValue([0, 2, 3, 2])을 실행한다고 가정하면, existingNumber는 0, 2, 3의 루프를 돌며 [1, undefined, 1, 1]이 된다.

그리고 마지막 원소인 2의 루프를 돌 때, existingNumber[2]이 undefined가 아닌 1이므로, if(existingNumber[array[i]] === 1)이 참이 돼 return true가 실행된다.

이 알고리즘의 단계 중 주요 유형은 existingNumber에서 해당 인덱스의 값이 1인지 확인하는 것이다. 배열에 중복 값이 없을 때가 최악의 시나리오이고, 이때 N번의 단계를 거치게 된다. 즉, O(N)인 알고리즘이다.

이 방식은 첫 번째 방식보다 메모리를 더 소비한다. 19장에서 상세히 다룬다.