알고리즘에서 매우 중요한 주제 중 하나인 빅오(Big-O)에 대한 개념 바로 잡기!
저는 실무에서 프로젝트를 진행할 때 오픈 날짜만 바라보고 개발하다 보면 시간에 많이 쫓기게 됩니다. 그래서 서비스 로직 성능에 대해서 깊게 생각하지 않고 결과물만 테스트하고 지나가는 일이 종종 발생하고 있죠. 이제 코딩 테스트도 종종 풀어볼겸 알고리즘을 공부하면서 자주 보게되는 빅오에 대한 개념을 파악하여 깊이 있는 알고리즘 공부를 시작하고자 이 글을 작성했습니다.
빅오(Big-O)
빅오 표기법은 입력 크키가 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법입니다. 특히 점근적 실행 시간(Asymptotic Running Time)을 표기할 때 가장 널리 쓰이는 수학적 표기법이죠. 여기서 점근적 실행 시간은 입력값 n이 무한대를 향할 때 lim 함수의 실행 시간 추이를 의미합니다. 점근적 실행 시간은 달리 말하면 시간 복잡도(Time Complexity)라고도 할 수 있습니다. 시간 복잡도는 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity)입니다. 그리고 이와 같은 계산 복잡도를 표기하는 대표적인 방법이 바로 빅오인 것이죠. 빅오의 개념을 정리하면 다음과 같습니다.
•
점근적 실행 시간을 표기하는 대표적인 수학적 표기법
•
점근적 실행 시간 = 시간 복잡도 = 계산 복잡도
•
구체적인 실행 속도보다는 실행 시간의 추이에 집중함
빅오 표기법 종류
이번에는 빅오 표기인 O(1), O( ), O(), O( ), O(), O(), O() 들을 살펴보고 각각 어떤 의미인지 알아보겠습니다. 각 표기법에 따른 시간 복잡도의 크기 차이는 아래와 같습니다.
O(1) < O( ) < O() < O( ) < O() < O() < O()
O(1)
입력값이 아무리 커도 실행 시간이 일정한 것을 의미합니다.
public int fn(int n) {
return 42;
}
Java
복사
위와 같이 상수를 반환하는 간단한 함수를 살펴보면, n의 크기가 얼마든 간에 일정한 상수를 반환하기 때문에 O(1)입니다.
O(1)이 실행되는 알고리즘의 예로는 배열에서 값을 조회할 때, 연결 리스트의 끝에 값을 삽입할 때와 해시 테이블의 조회 및 삽입 등이 있습니다.
O( )
여기서부터 실행 시간은 입력값에 영향을 받습니다. 아래 함수는 n의 값을 계속해서 반으로 나누고 있는데, 연산 횟수가 의 계산 결과와 동일합니다. 컴퓨터과학에서는 주로 밑인 2를 생략하여 log n으로 표현합니다.
public int fn(int n) {
while(n > 1)
n /= 2;
return n;
}
Java
복사
log는 매우 큰 입력값에도 크게 영향을 받지 않는 마법과 같은 함수이기 때문에 웬만한 크기의 n에 대해서도 매우 견고합니다. 그래서 O(log n)이 실행되는 알고리즘은 사실상 최고의 알고리즘이라 할 수 있습니다. 대표적으로 이진 탐색(Binary Search)가 이에 해당합니다.
정확히 입력값(n)의 크기만큼 실행 시간에 영향을 받습니다. 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례하게 됩니다.
O()
public int fn(int n) {
int r = 0;
for (int i = 0; i < n; i++)
r++;
return r;
}
Java
복사
위 함수는 입력값만큼 연산하는 함수입니다. 즉, 정확히 n의 크기만큼 연산을 진행합니다. 실행 시간이 선형(Linear)으로 증가하기 때문에 O(n) 알고리즘을 선형 시간(Linear-Time) 알고리즘이라고도 합니다. 정렬되지 않은 리스트에서 최대값 또는 최솟값을 찾는 경우가 이에 해당합니다. 왜냐하면 정렬되지 않은 리스트에서 최대값, 최소값을 찾기 위해서는 모든 입력값을 적어도 한 번은 살펴봐야 하기 때문에 정확히 (O)n이 됩니다.
O( )
입력값만큼 순회하며 log n의 연산이 곱해집니다. 다음 함수는 입력값만큼 순회하면서 각 순서에 해당하는 값을 반으로 나눠가며 연산하는 함수입니다.
public int fn(int n) {
int r = n;
for (int i = 0; i < n; i++) {
while (n > 1)
n /= 2;
n = r;
}
return r;
}
Java
복사
이 함수는 입력값 n의 크기만큼 순회하면서, 다시 입력값을 반으로 나눠가며 log n의 연산을 진행합니다. 병합 정렬(Merge Sort)을 비롯한 효율적인 정렬 알고리즘이 이에 해당합니다. 적어도 모든 수에 대해 한 번 이상을 비교해야 하는 비교 기간 정렬 알고리즘은 아무리 좋은 알고리즘도 O(n log n)보다 빠를 수 없습니다.
이 외에도 O(n log n)은 특별한 의미가 있는데, 로그의 마법과 같은 특징 때문에 log n은 좀처럼 큰 수가 나오질 않아 실용적인 관점에서 O(n)이나 O(n log n)은 사실상 비슷한 성능으로 가정해도 무방합니다. 그래서 좋은 알고리즘이라 칭하는 대부분이 이 범주에 듭니다.
O()
입력값의 제곱만큼 연산합니다. 아래는 입력값을 중첩으로 반복하면서 연산하는 함수입니다.
public int fn(int n) {
int r = 0;
for (int i = 0; i < n; i++) {
for(int j = 0; j < n; j++)
r += j;
}
return r;
}
Java
복사
이 함수는 n의 크기만큼 다시 n번 연산을 진행하므로 버블 정렬(Bubble Sort) 같은 비효율적인 정렬 알고리즘이 이에 해당합니다. 알고리즘 문제를 풀 때, 입력값이 클 경우 부터는 실행 시 타임아웃이 발생하는 경우가 잦습니다. 그래서 알고리즘을 최적화한다고 하면 O()을 O(n log n)으로 줄이는 과정을 동반합니다.
O()
입력값의 크기만큼 2배씩 연산합니다. 아래와 같이 피보나치(Fibonacci) 수를 재귀로 계산하는 알고리즘을 예로 들 수 있습니다.
public int fn(int n) {
if (n <= 1)
return n;
else
return fn(n-1) + fn(n -2);
}
JavaScript
복사
위 함수는 번만큼 연산을 진행합니다. 정확히는 정도 되지만 피보나치 수를 얘기 할 때는 단순하게 으로 언급해도 충분합니다. 간혹 과 혼동하는 경우가 있는데, 비슥해 보이지만 쪽이 훨씬 더 큽니다. 은 정확히 로그를 반대로 뒤집은 값으로 보면 되는데, 로그가 마법처럼 줄어드는 값이라면 반대로 은 마법처럼 늘어나는 값이므로 그만큼 사용에 유의해야 합니다. n이 조금만 커져도 사실상 적용하기 어려운 알고리즘입니다.
O()
입력값을 1씩 줄여가며 곱셈 연산을 합니다. 아래의 함수를 예를 들어보겠습니다.
public int fn(int n) {
for (int i = 0; i < n; i++)
fn(n -1)
return n;
}
JavaScript
복사
위 함수는 입력값의 크기만큼 순회하면서, 다시 입력값을 1씩 줄여가며 재귀 호출하는 함수입니다. 여러 번 재귀 호출을 하면서 실제로는 fn() 함수 호출을 모두 합하면 약 2.7 * n! 만큼 호출하는데, 여기서 상수 항을 제외하면 시간 복잡도는 O()입니다. 각 도시를 방문하고 가장 짧은 경로를 찾는 외판원 문제(Travelling Salesman Problem)를 브루트 포스로 풀이할 때가 이에 해당합니다. O()은 가장 느린 알고리즘으로, 입력값이 조금만 커져도 웬만한 다항 시간 내에는 계산이 어렵죠. 그렇기 때문에 이 또한 실무에서 적용하기 어려운 알고리즘입니다.
자바 컬렌션 프레임워크의 빅오
자바가 제공하는 대표적인 다용도 자료형인 자바 컬렉션 프레임워크의 시간 복잡도 비교를 표로 정리해봤습니다.
리스트
연산 | ArrayList | LinkedList |
인덱스 끝에 삽입 | O(1) 가끔 O(n) | O(1) |
인덱스 중간에 삽입 | O(n) | 탐색 O(n), 삽입 O(1) |
인덱스 끝에서 삭제 | O(1) | O(1) |
인덱스 중간에서 삭제 | O(n) | 탐색 O(n), 삭제 O(1) |
조회 | O(1) | O(n) |
맵
연산 | HashMap | LinkedHashMap |
추가 | O(1) | O(1) |
삭제 | O(1) | O(1) |
조회 | O(1) | O(1) |
데크
연산 | ArrayDeque | LinkedList |
삽입 | O(1) | O(1) |
추출 | O(1) | O(1) |
마치며
이렇게 빅오에 대해 공부한 내용을 정리해봤습니다. 글이 너무 길어져 상한과 최악, 분할 상환 분석 개념에 대해서 작성하지 않았지만 빅오를 좀 더 자세히 공부하고 싶은 분은 상한, 최악, 분할 상환 분석 개념도 같이 살펴보시면 더 재밌게 공부할 수 있을 겁니다! 시간이 나면 저도 한 번 정리해서 작성해 봐야겠습니다.
References
•
박상길, 『자바 알고리즘 인터뷰 with 코틀린』, 책만(2023), p169-186.
More posts like this
Search