빅오는 알고리즘 공부를 하면 반드시 다루는 중요한 주제이다. Computer science에서 빅오는 입력값이 커질 때 알고리즘 실행 시간(시간복잡도), 공간 요구사항(공간 복잡도)가 어떻게 증가하는지를 분류하는 데 사용된다. 즉 알고리즘이 얼마나 효율적인지 판단하는 지표라는 것을 의미한다. 이번 포스팅에서 빅오로 알고리즘의 효율성을 어떻게 표현하는 지 알아보자.
빅오(Big-O)란 입력이 무한대로 커질때 함수의 상한을 설명하는 수학적 표기 방법을 일컫는다. 실행 시간의 관점에서는 점근적 실행 시간을 표기한다(= 시간 복잡도)라고 하는데 쉽게 설명하면 입력값 n이 커질 때(무한대를 향할때), 함수의 실행 시간의 추이를 의미한다고 보면 된다. 컴퓨터의 연산 능력으로 인해 아무리 복잡한 알고리즘이라도 입력의 크기가 작으면 금방 돌아가기 때문에 빅오에서 관심 있는 것은 입력의 크기이다. 입력이 큰 경우에는 알고리즘의 효율성에 따라 수행 시간에 큰 차이가 있을 것이다.
1. 빅오로 시간 복잡도를 표현하는 방법
시간 복잡도는 앞서 살펴본대로 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도를 의미한다. 이때 이 계산 복잡도를 빅오로 표현하게 된다.
예를 들어 입력값 n에 대하여 $4n^3+3n^2+6$ 번 계산이 실행되는 함수가 있다고 한다면 빅오는 최고차항인 $4n^3$만을 고려하여 O($n^2$)으로 표기한다. 다음과 같은 빅오 표기법이 있다.
- O(1)
- O(log n)
- O(n)
- O(n log n)
- O($n^2$)
- O($2^n$)
- O(n!)
각 표기법은 순서대로 효율적이라고 볼 수 있다. 단순하게 n, $2^n$에 각각 100을 대입해보면 큰 차이가 나는 것을 알 수 있을 것이다.(클 수록 그 차이는 더 커짐)
시간 복잡도 이외에도 공간 복잡도도 빅오로 표현가능하다.
2. 빅오, 빅오메가, 빅세타란?
빅오(Big-O), 빅오메가(Big-Ω), 빅세타(Big-Θ)는 알고리즘의 실행 상한,하한 그리고 평균을 의미한다.
가장 빨리 실행될 때 하한, 가장 늦게 실행될 때는 상한을 뜻하며 각각 빅오메가, 빅오로 지칭한다. Chatgpt에게 물어보니 요약을 해줘서 표를 가져와봤다.
이러한 표현은 반은 맞고 반은 틀리다.
상한을 최악의 경우와 혼동하기 쉽다. 그러나 상한을 나타내는 빅오 표기법은 정확하게 표현하지 못하는 함수(알고리즘)에 대하여 적당히 정확하게 표현하는 방법이지 최악의 시간 복잡도와는 상관이 없는 개념이다.
퀵 정렬을 예를 들어 설명하면 입력값이 [1, 4, 3, 7, 8, 6, 5] 일 때 퀵정렬 최선의 경우에 해당한다. 퀵정렬을 수행하면 총 18번의 비교, 스왑 연산이 이뤄진다. 반면 입력값이 [1, 2, 3, 4, 5, 6, 7]이면 총 48번의 연산이 이뤄진다. 이 경우가 최악의 시간 복잡도인 경우이다.
최선의 경우에 대하여 가장 fit하게 상한을 나타냈을 때 O(n log n), 최악의 경우에 대하여 가장 fit하게 상한을 나타내면 O($n^2$)가 될 것이다.
정리하면 빅오 표기법은 주어진 경우(최선/최악/평균) 경우의 수행 시간의 '상한'을 나타내는 것이다. 그래서 정의적으로는 퀵정렬의 예시에서 최선의 경우 O($n^3$)도 맞는 표현이다. 그러나 아무의미가 없기 때문에 fit하게 나타낸다.
참고자료
[1] 빅오 개념: https://developer-cat.tistory.com/3
'Study > 코딩테스트' 카테고리의 다른 글
| 연습문제: 다음 큰 숫자 / 월간 코드 챌린지 시즌1: 두 개 뽑아서 더하기 (1) | 2023.07.04 |
|---|---|
| 연습 문제: 최댓값과 최솟값, 푸드 파이트 대회 (1) | 2023.05.22 |
| 2017 팁스타운: 짝지어 제거하기 / 연습문제: 크기가 작은 부분 문자열, 이상한 문자 만들기 (1) | 2023.05.15 |
| 연습문제: 하샤드 수, 콜라츠 추측 / 스택,큐: 올바른 괄호 (2) | 2023.05.05 |
| 연습 문제: 삼총사 / 스택,큐: 같은 숫자는 싫어 (1) | 2023.04.17 |