누구나 자료구조와 알고리즘 - (4) 빅 오로 코드 속도 올리기

 

 

 

 

 

 

 

버블 정렬(Bubble sort)

 

1.1. 버블 정렬 알고리즘

이런 배열이 주어졌을 때 버블 정렬 알고리즘이 어떻게 동작하는지 보자.

[2, 1, 3, 5]

 

1. 배열내에서 연속된 두 항목을 가리킨다. 처음에는 배열의 첫 원소부터 시작한다.

[2, 1, 3, 5]

 

2. 두 항목의 순서가 바뀌어있으면 두 항목을 교환하며, 순서가 올바르다면 아무것도 하지 않는다.

[1, 2, 3, 5]

 

3. 포인터를 오른쪽으로 한 셀씩 옮긴다.

[1, 2, 3, 5]

 

4. 배열의 끝까지 이 단계를 반복한다. 이를 패스스루(pass-through)라 한다. 끝나면 다시 처음 두 값으로 옮겨서 1~3단계를 다시 실행함으로써 새로운 패스스루를 실행한다. 교환이 일어나지 않는 패스스루가 생길 때 까지 패스스루를 반복한다.

 

 

 

 

1.2. 버블 정렬 알고리즘의 효율성

버블 정렬 알고리즘은 두 가지 중요한 단계를 포함한다.

• 비교: 어느 쪽이 더 큰지 두 수를 비교한다.
• 교환: 정렬하기 위해 두 수를 교환한다.

버블 정렬에서 얼마나 많은 비교가 일어나는지 알아보자.

데이터 원소가 5개라면 최대 20개의 단계가 필요하며, 80개의 경우에는 6320개의 단계가 필요하다.

 

이걸 빅 오 표기법으로 나타내면 버블 정렬의 효율성은 O(N²)이다. (이차 시간이라고도 불린다.)

그래프로 표현하면 단순한 대각선을 그리는 O(N)과 비교했을 때 데이터가 늘어날 수록 매우 급격하게 그려지는 것을 알 수 있다.

 

 

 

 

1.3. 선형 해결법

배열에 중복숫자가 들어있는지 확인하는 함수를 작성하면 중첩 루프를 이용할 수 있다.

export const hasDuplicateValue = (array) => {
  let steps = 0 // 단계의 수
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; j++) {
      steps++ // 단계수를 증가시킨다.
      if(i !== j && array[i] === array[j]) {
        return true
      }
    }
  }

  console.log('단계 수 >>> ', steps);
  return false;
}

 

[1, 4, 5, 2, 9]로 실행하면 단계수는 25단계가 된다. 총 25번의 비교가 있었음을 의미한다.

중첩 루프를 사용하는 경우는 대부분 O(N²)으로 전형적으로 느린, 비효율적인 알고리즘임을 기억해야 한다.

 

 

중첩 루프를 사용하지 않는 방법을 보자.

배열을 검사할 때 빈 배열의 찾는 값의 인덱스에 1이라는 값을 삽입하며 순회하며 중복값을 찾는다.

export const hasDuplicateValue = (array) => {
  let steps = 0 // 단계의 수
  let existingNumbers = []
  for (let i = 0; i < array.length; i++) {
    steps++ // 단계수를 증가시킨다.
    if (existingNumbers[array[i]] === 1) {
      return true
    } else {
      existingNumbers[array[i]] = 1
    }
  }

  console.log('단계 수 >>> ', steps);
  return false;
}

 

[1, 4, 5, 2, 9]로 실행하면 단계수는 5단계가 된다.

이 알고리즘은 O(N)이 되며, 기존에 중첩 루프를 사용하여 구현했던 O(N²)보다 훨씬 빠른 알고리즘이 된다.

 

 

---

출처

제이 웹그로우, 누구나 자료구조와 알고리즘 (길벗, 2021)

 

 

 

 

---

개인적으로 공부한 내용을 정리하는 블로그로
잘못된 개념을 게시하지않도록 주의하고 있으나 오류가 있을 수 있습니다.