빅-오(Big-O)는 무엇일까?
간단하게 설명하면 알고리즘의 효율성을 나타내는 지표 혹은 언어입니다. Big-O를 확실히 이해하고 있어야 알고리즘을 구현할 때 큰 고비를 해결할 수 있습니다. 또한, Big-O에 대한 개념을 몰라 난처한 상황에 놓이거나 본인 코드의 개선점을 절대 찾지 못할 수도 있으니 꼭 이해하고 숙지했으면 합니다.
시간복잡도란?
여러분들이 택배 기사라고 가정해 봅니다. 수많은 택배 물량을 해소하려면 택배 차량의 최대 적재량으로 배송하며 빠른 시간 내에 모든 가정에 배달을 완료해야 할 것입니다. 이 상황에서 택배의 물량이 감당하지 못할만큼 쏟아진다면 여러분들은 어떻게 할 것 같나요? 택배 차량의 수를 늘리든지 조금이라도 더 빨리 배송하면서 하나의 택배라도 더 배달하려고 할 것입니다. 여기서, 택배 차량의 적재량을 늘릴 수 있게 공간을 늘린다고 하거나 택배 차량의 성능을 업그레이드 또는 비행기로 운반한다면 먼 거리를 보다 빠른 속도로 더 많은 택배를 배송할 수 있을 것입니다.
이것이 바로 점근적 실행 시간(Asymptotic runtime), 또는 Big-O 시간에 대한 개념입니다.
1. 택배 배송
O(n) - n이 배송해야 할 물품이라고 생각해봅시다. 택배 물량이 늘어나면 늘어날수록 배송 시간 또한 선형적으로 증가합니다.
2. 비행기 배송 또는 택배 차량 성능 상승
O(1) - 배송 물량에 상관없이 일정한 시간으로 배송 예정일에 맞춰 배송을 끝마칠 수 있습니다. 즉, 상수시간만큼 소요됩니다.
여기서 선형식은 시간이 어떻게 흐르든 결국 상수를 뛰어넘게 됩니다. 이 외에도 다양한 실행 시간이 존재합니다.
O(logN), O(NlogN), O(N), O(N^2), O(2^N) 등이 있으며 너비가 w미터이고 높이가 h미터인 울타리를 색칠하는 시간을 O(wh)로 표기할 수 있으며 p번의 페인트를 덧칠한다면 O(whp)의 시간이 소요됩니다.
💡
Big-O : 시간의 상한을 나타냅니다. (최악의 경우)
Big-θ : 등가 개념 또는 하한을 나타냅니다. (최선의 경우)
Big-Ω : 빅오와 빅세타 둘 다 의미합니다. (평균의 경우)
최선의 경우, 최악의 경우, 평균적인 경우
퀵 정렬을 예로들어 살펴보겠습니다. 퀵 정렬은 ‘축'이 되는 원소 하나를 무작위로 뽑은 뒤 이보다 작은 원소들은 앞에, 큰 원소들은 뒤에 놓이도록 원소의 위치를 바꿉니다. 그 결과 ‘부분 정렬'이 완성되고, 그 뒤 왼쪽과 오른쪽 부분을 이와 비슷한 방식으로 재귀적으로 정렬해 나갑니다.
- 최선의 경우
- 만약 모든 원소가 동일하다면 퀵정렬은 평균적으로 한 차례만 순회하고 끝날 것입니다. [O(N)]
- 최악의 경우
- 배열에서 가장 큰 원소가 계속해서 축이 된다면 재귀 호출이 배열을 절반 크기의 부분 배열로 나누지 못하고 고작 하나 줄어든 크기의 부분 배열로 나누게 됩니다.[O(N^2)]
- 평균적인 경우
- 위와 같이 최선과 최악의 경우가 흔히 발생하는 것은 아닙니다. [O(NlogN)]
공간복잡도란?
알고리즘에서는 시간뿐 아니라 메모리(혹은 공간) 또한 신경써야 합니다.
공간복잡도는 시간 복잡도와 평행선을 달리는 개념입니다. 크기가 n인 배열을 만들고자 한다면 O(n)의 공간이 필요합니다.
n x n 크기의 2차원 배열을 만들고자 한다면 O(n^2)의 공간이 필요합니다.
재귀 호출에서 사용하는 스택 공간 또한 공간 복잡도 계산에 포함됩니다.
상수항은 무시!
Big-O는 단순히 증가하는 비율을 나타내는 개념이므로 특수한 입력에 한해 O(N) 코드가 O(1) 코드보다 빠르게 동작하는 것은 가능성이 있습니다.
이런 이유로 수행 시간에서 상수항을 무시합니다. 즉 O(2N)이든 O(64N)이든 O(N)으로 표기합니다.
하지만, O(N)이 언제나 O(2N)보다 나은 것은 아닙니다.
지배적이지 않은 항은 무시!
O(N^2+N)과 같은 수식이 있을 때는 어떻게 해야 할까요? 두번째 N은 상수항은 아니지만 특별히 중요한 항도 아닙니다.
O(N^2+N^2)은 O(N^2)가 됩니다. N^2항을 무시해도 된다면 그보다 작은 N항은 무시해도 됩니다.
💡
O(N^2+N)은 O(N^2)이 된다.
→ O(N+logN)은 O(N)이 된다.
→ O(5*2^N+1000N^100)은 O(2^N)이 된다.
위 그래프와 같이 O(N^2)은 O(N)보다 맣이 느리지만 O(2^N)이나 O(N!)보다는 느리지 않고, 최악의 경우보다 느린 경우는 생각보다 많습니다.
for (let i = 0; i < 5; i++) {
console.log(i);
}
for (let j = 0; j < 5; j++) {
console.log(j);
}첫번째 코드입니다. 이 코드에서는 A의 일이 끝마쳐진뒤 B의 일을 수행합니다. 시간복잡도는 O(I+J)가 됩니다.
for (let i = 0; i < 5; i++) {
for (let j = 0; j < 5; j++) {
console.log(i + " " + j);
}
}두번째 코드입니다. 이 코드에서는 A의 각 원소에 대해 B의 일을 수행합니다. 시간복잡도는 O(I*J)가 됩니다.
즉, 첫번째 코드의 형태라면 수행 시간을 더하는 형태이고, 두번째 코드의 형태라면 수행 시간을 곱해야 합니다.
상환 시간
ArrayList(동적 가변크기 배열)는 배열의 역할을 함과 동시에 크기가 자유롭게 조절되는 자료 구조입니다.
배열이 가득 차 있는 경우를 생각해보면 배열에 N개의 원소가 들어있을 때 새로운 원소를 삽입하려면 O(N)이 걸립니다. 크기가 2N인 배열을 새로 만들고 기존의 모든 원소를 새 배열로 복사해야 하기 때문입니다. 따라서 이 경우 삽입 연산은 O(N) 시간이 소요됩니다.
하지만, 배열이 가득 차 있는 경우는 극히 드물기에 대다수의 경우에는 배열에 가용 공간이 존재하고 이때의 삽입 연산은 O(1)이 걸립니다.
최악의 경우는 가끔 발생하지만 한번 발생하면 그 후로 꽤 오랫동안 나타나지 않으므로 수행 시간을 분할 상환한다는 개념입니다.
즉, 1에서 X까지 2배씩 증가하는 수열과 X에서 1까지 절반씩 감소하는 수열을 분할 상환해보면 결국 필요한 시간은 O(1)이다.
logN 수행 시간
이진 탐색을 생각해봅니다. 이진 탐색은 N개의 정렬된 원소가 들어있는 배열에서 원소 x를 찾을 때 사용됩니다.
먼저 원소 x와 배열의 중간값을 비교합니다. ‘x===중간값’을 만족하면 이를 반환합니다. ‘x < 중간값'일 때는 배열의 왼쪽부분을 재탐색하고 ‘x > 중간값'일 때는 배열의 오른쪽 부분을 재탐색합니다.
N을 절반씩 나누는 과정에서 몇 단계만에 1이 되는지에 따라 결정됩니다.
즉, 2^k = N을 만족하는 k는 로그(log)입니다.
💡 2^4 = 16 → log16 = 4, logN = k → 2^k = N
어떤 문제에서 원소의 개수가 절반씩 줄어든다면 그 문제의 수행 시간은 O(logN)이 될 가능성이 큽니다.
같은 원리로, 균형 이진 탐색 트리에서 원소를 찾는 문제도 O(logN)입니다. 매 단계마다 원소의 대소를 비교한 뒤 왼쪽 혹은 오른쪽으로 내려갑니다. 각 단계에서 검색해야 할 노드의 개수가 절반씩 줄어들게 되므로, 문제 공간 또한 절반씩 줄어듭니다.
재귀적으로 수행 시간 구하기
function func(n) {
if (n <= 1) {
return 1;
}
return func(n - 1) + func(n - 1);
}
console.log(func(n));이 코드를 보고 함수가 두번 호출되었으니 O(N^2)이라고 생각할 수 있는데 틀렸습니다.
전체 노드의 개수는 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + ... + 2^N (= 2^(N+1) -1)이 됩니다.
여기서 다수의 호출로 이루어진 재귀 함수에서 수행 시간은 보통 O(분기(재호출)^깊이)로 표현됩니다.
따라서, 위 수행 시간은 O(2^N)이 됩니다.
이 알고리즘에서 공간복잡도는 O(N)이 될 것입니다. 전체 노드의 개숮는 O(2^N)이지만 특정 시각에 사용하는 공간의 크기는 O(N)입니다.
테크톡 발표 영상
최근댓글