누구나 자료구조와 알고리즘 - (5) 빅 오를 사용하거나 사용하지 않는 코드 최적화

 

 

 

 

 

 

빅 오는 알고리즘을 서로 비교하고 주어진 상황에 알맞은 알고리즘을 결정하게 해주는 도구이지만 유일한 도구는 아니다.

빅 오 표기법에서는 한 알고리즘이 다른 알고리즘보다 훨씬 빠른 경우에도 두 경쟁 알고리즘을 똑같은 방식으로 표기하기도 한다.

 

 

---

 

 

선택 정렬(selection sort)

 

1.1. 선택 정렬(selection sort)이란?

1단계. 값을 왼쪽 → 오른쪽으로 확인하며 어떤 값이 최솟값인지 결정한다.

2단계. 최솟값이 정해졌다면 가장 패스스루를 처음 시작했을 때의 값과 교환한다.

두번째 패스스루는 인덱스 1부터 시작하게 된다.

 

매 패스스루는 1, 2단계를 반복하며 배열 끝에서 시작하는 패스스루에 도달할 때 까지 반복한다.

 

 

1.2. 선택 정렬의 효율성

export const selectionSort = (array) => {
  for (let i = 0; i < array.length; i++) {
    let lowestNumberIndex = i
    for (let j = 0; j < array.length; j++) {
      if (array[j] < array[lowestNumberIndex]) {
        lowestNumberIndex = j
      }

      if (lowestNumberIndex != i) {
        let temp = array[i]
        array[i] = array[lowestNumberIndex]
        array[lowestNumberIndex] = temp
      }
    }
  }

  return array;
}

 

선택 정렬은 버블 정렬보다 단계 수가 반 정도 적은 알고리즘으로 두 배 더 빠르므로 O(N² / 2)로 표기하면 되지 않을까 싶지만, 빅 오 표기법에서 선택 정렬은 O(N²)으로 표기된다.

 

이유는 빅 오 표기법은 상수를 무시하기 때문으로 지수가 아닌 수는 포함하지 않기때문에 "/ 2"는 버려진다.

ex) N / 2 단계가 필요한 알고리즘은 O(N)으로, N² + 10단계가 필요한 알고리즘은 10을 버리고 O(N²)으로, O(N)보다 100배나 느린 O(100N)이라 해도 마찬가지로 O(N)으로 표현한다.

 

빅 오의 카테고리는 O(1), O(logN), O(N), O(N²)처럼 서로 차이가 큰 경우로 나뉘어져 있다.

O(N)과 O(2N)은 카테고리 간의 차이에 비하면 유의미한 차이가 아니기 때문에 하나의 카테고리이다.

 

 

---

출처

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

 

 

 

 

---

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