Big O 표기법 | Big O Notation
껄껄껄
코딩무새입니다.

자료구조 공부를 하다 보면 듣고 싶지 않아도, 보고 싶지 않아도 알게 되는 Big O입니다.
Big O 표기법이란 뭘까요?
코딩무새가 설명해 보겠습니다.
Big O 표기법?
Big O 표기법은 시간 복잡도를 표현하는 방법 중 하나입니다.
시간 복잡도는 입력 크기에 따라 알고리즘이 실행되는 연산 횟수를 수학적으로 분석하는 개념이라고 생각해 주시면 됩니다. 입력 크기가 증가할 때 실행 시간이 어떻게 변하는지를 분석하는 것이죠.
Big O 표기법을 이해한다면 로직을 구현함에 있어 어떤 방식이 더 효율적인지 판단할 수 있게 됩니다.
Big O 시간 복잡도 종류
Big O 표기법의 종류입니다.
아래로 내려갈수록 시간이 더 오래 걸린다고 생각하면 됩니다.
시간복잡도 | 설명 | 예제 |
O(1) | 입력 크기에 상관없이 실행 시간이 일정 | 배열에서 특정 인덱스 조회 |
O(log n) | 입력이 2배가 되어도 실행 시간은 조금만 증가 | 이진 탐색(Binary Search) |
O(n) | 입력 크기에 비례하여 실행 시간 증가 | 단순 반복문 |
O(n log n) | 효율적인 정렬 알고리즘(Merge Sort, Quick Sort) | 정렬 알고리즘 |
O(n²) | 중첩된 반복문 | 버블 정렬, 선택 정렬 |
O(2ⁿ) | 재귀 호출이 기하급수적으로 증가 | 피보나치 재귀 |
O(n!) | 순열, 조합 (Brute-force) | TSP |
그래프로 확인해 볼까요?
각 시간복잡도에 대한 그래프입니다.
입력이 커질수록 효율이 안 좋은 경우가 보이네요.
개발하실 때 O(n log n) 밑으로 시간복잡도가 측정된다면 그것은 그렇게 좋은 로직이 아니라고 생각되네요.

O(1)
어떤 입력이 들어와도 걸리는 시간은 동일합니다.
매우 효율적이고 사기적이죠.
대표적으로는 배열에서 인덱스로 값을 찾는다거나, 해시, 스택 및 큐의 pop, push가 있겠네요.
O(log n)
로그 시간이라고 합니다.
입력 크기가 증가해도 데이터의 크기가 절반 감소하기 때문에, 실행 시간이 완만하게 증가하는 알고리즘입니다.
예로는 binary search 알고리즘, tree 형태 자료구조 탐색
O(n)
선형 시간입니다.
입력 크기가 증가하면 실행 시간도 동일한 비율로 증가하는 알고리즘입니다.
for 문이 대표적이네요.
O(n log n)
O(n)의 알고리즘과 O(log n)의 알고리즘이 중첩된 형태로 효율적인 정렬 알고리즘이 사용하는 방식인데요.
대표적으로 Merge Sort, Quick Sort 같은 유명한 알고리즘들이 있죠.
O(n²)
이차 시간입니다.
중첩된 반복문을 사용하여 모든 요소를 비교하는 알고리즘이라고 설명할 수 있을 거 같네요.
이중 for문이나 버블 정렬 알고리즘이 이에 해당합니다.
O(2ⁿ)
입력 크기가 커질수록 실행 시간이 기하급수적으로 증가하는 알고리즘입니다.
재귀적 피보나치 함수 같은 코딩 테스트 문제가 존재하는데요.
실전에서는 피해야 합니다.
사용하면.. 서버가 눈물을 흘릴 거예요.
O(n!)
팩토리얼 시간입니다.
모든 경우의 수를 탐색하는 브루트포스 알고리즘이 이에 해당합니다.
입력이 조금만 커져도 계산 불가능한 수준으로 연산량이 커집니다.
Big O 표기법에 대해서 알아보았는데요.
알고 가면 평생 써먹을 수 있으니 알아두어야 합니다.
껄껄껄