빅오(Big-O) 표기법

개발 공부/알고리즘

가욤이 2024. 1. 11. 01:05

빅오(Big-O)란,

코드에서 데이터가 늘어날 때 알고리즘의 성능을 표기하는 방법이다.

단순히 코드가 '좋다', '나쁘다'로 표현하는 것이 아닌 숫자로 코드의 성능을 표기하기 위해 빅오 표기법을 사용한다.

입력의 크기와 실행 시간과의 관계라고 할 수 있다.

데이터 원소가 N개일 때 알고리즘은 몇 단계가 필요할까?

위의 그래프에서 x축을 데이터 수로 봤을 경우, O(N)의 그래프는 데이터의 수가 늘어날수록 알고리즘 단계도 늘어난다.

즉, 데이터가 1000개가 되면 알고리즘도 1000단계가 걸린다.

O(1)의 그래프를 보면 데이터가 1개이거나 1000개이거나 알고리즘은 항상 100단계가 걸린다.

데이터가 100개 미만일 경우엔 O(N)이 빠를 수 있겠지만, 그 이상으로 넘어가면 O(N)의 알고리즘이 훨씬 많은 단계를 거쳐야 한다는 것을 알 수 있다.

O(100)이 아닌 O(1)로 표기하는 이유는 데이터가 늘어날 때 단계 수가 어떻게 증가하는지를 설명하는 것이 빅 오이기 때문이다.

100단계를 하던, 1단계를 하던 데이터 증가에 영향을 받지 않기 때문에 본질적으로 같은 알고리즘이다.

function logAtLeast5(n) {
  for(let i=1; i<=Math.max(5,n); i++) {
    console.log(i)
  }
}

위 코드는 인자로 5이하의 값을 받을 경우 코드가 총 5번 실행이 되며, 그 이상의 값을 인자로 받으면 코드가 n번 실행하게 되는 함수이다.

따라서 O(N)인 알고리즘이라 할 수 있다.

function logAtMost5(n) {
  for(let i=1; i<=Math.min(5,n); i++) {
    console.log(i)
  }
}

위 코드는 인자로 5이상의 값을 받아도 항상 5번만 실행된다. 따라서 위 알고리즘은 O(1)의 성능을 가진다.

: 객체와 배열은 알고리즘 문제를 해결할 때 가장 많이 사용하는 자료구조이다.

따라서, 알고리즘 문제를 효율적으로 해결하기 위해 객체/배열을 접근하거나 입력, 제거 등의 연산을 수행할 때의 알고리즘의 성능이 어떻게 되는지 파악할 필요가 있다.

객체는 정렬이 필요가 없고, 빠른 접근과 입력/제거를 원할 때 사용한다.

배열은 정렬이 필요한 자료구조이다.

: 상수 값은 알고리즘 평가 단계에 영향을 거의 주지 않는다.

: 데이터가 많아질수록 알고리즘 평가에 영향을 주지 않기 때문에 무시한다.

데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘

로그(log)란, 지수와 역의 관계이다.

2를 몇 번 곱해야 8을 얻을 수 있는지를 뜻한다. 총 3번이므로 3이 나온다.

다시 말해서, 8을 1이 될 때까지 계속 2로 나눴을 때 총 3번이 걸린다는 의미이다.

밑이 2인 로그는 생략해서 표현할 수 있다.

이러한 로그의 수식에 의해 O(logN)은 원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계 수가 걸린다는 뜻이다.

logN의 성능을 갖는 대표적인 알고리즘으로 탐색 알고리즘 중에 이진 탐색이 있다.