알고리즘을 공부하다 보면 가장 먼저 만나게 되는 개념이 바로 '빅오 표기법'입니다. "이 알고리즘의 시간 복잡도는 O(n)입니다", "O(log n)이 더 효율적입니다"와 같은 표현을 들어보셨을 텐데요. 이번 포스팅에서는 빅오 표기법이 무엇이고, 왜 중요한지, 그리고 실제로 어떻게 활용하는지 알아보겠습니다.
알고리즘 복잡도란?
알고리즘의 효율성을 평가하는 데는 공간 복잡도와 시간 복잡도 두 가지 기준이 있습니다.
공간 복잡도 (Space Complexity)
공간 복잡도는 알고리즘이 실행되는 동안 사용하는 메모리 공간을 나타내는 개념입니다.
주요 특징
- 데이터 관리에 필요한 메모리 공간을 분석합니다.
- 입력 데이터의 크기에 따라 메모리 사용량이 어떻게 변하는지 측정합니다.
- 변수, 배열, 재귀 호출 스택 등이 차지하는 공간을 모두 포함합니다.
요즘 공간 복잡도를 덜 중요하게 여기는 이유?
과거와 달리 현대의 하드웨어 성능이 비약적으로 발전했습니다. 메모리 가격이 저렴해지고 용량이 커지면서 대부분의 일반적인 알고리즘에서는 메모리 부족 문제가 거의 발생하지 않습니다. 따라서 현업에서는 시간 복잡도를 훨씬 더 중요하게 다룹니다.
물론 임베디드 시스템이나 메모리가 제한된 환경, 혹은 빅데이터 처리와 같이 대용량 데이터를 다루는 경우에는 여전히 공간 복잡도가 중요합니다.
시간 복잡도 (Time Complexity)
시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간을 나타내는 개념입니다.
주요 특징
- 알고리즘이 데이터를 처리하는 데 필요한 연산 횟수를 측정합니다.
- 실제 실행 시간이 아닌, 입력 크기에 따른 연산 횟수의 증가율을 나타냅니다.
- 점근 표기법(Asymptotic Notation)으로 표현합니다.
왜 실제 시간이 아닌 연산 횟수일까?
실제 실행 시간은 하드웨어 성능, 프로그래밍 언어, 컴파일러 최적화 등 다양한 외부 요인에 영향을 받습니다. 따라서 알고리즘 자체의 효율성을 객관적으로 평가하기 위해 연산 횟수의 증가 추세를 분석합니다.
여기까지, 복잡도의 두 가지 기준에 대해서 살펴보았을때 요약하자면 아래와 같습니다.
시간 복잡도: 실행의 효율성공간 복잡도: 메모리의 효율성
점근 표기법 (Asymptotic Notation)
그렇다면 알고리즘의 연산 횟수를 어떻게 표현해야 할까요?
예를 들어 어떤 알고리즘의 연산 횟수가 정확히 3n² + 5n + 10번이라고 해봅시다. 하지만 실제로 우리가 알고 싶은 것은 "입력이 커지면 얼마나 느려질까?"입니다. n이 1000, 10000으로 커질수록 3n² 부분이 압도적으로 커지고, 5n이나 10은 거의 의미가 없어집니다.
이처럼 데이터가 충분히 클 때 알고리즘이 어떻게 동작하는지를 간단하고 명확하게 표현하기 위해 점근 표기법을 사용합니다. 복잡한 수식 대신 핵심만 남겨서 알고리즘의 효율성을 한눈에 비교할 수 있게 해주는 것입니다.
점근 표기법은 알고리즘의 성능을 수학적으로 표현하는 방법입니다.
점근 표기법의 핵심 원칙
1. 가장 큰 영향력을 가진 항만 표시합니다
예를 들어 알고리즘의 연산 횟수가 3n² + 5n + 10이라면, n이 커질수록 n² 항이 전체 값을 지배하게 됩니다. 따라서 O(n²)로 표기합니다.
2. 상수항은 무시합니다5n이든 100n이든 모두 O(n)으로 표기합니다. 입력 크기가 커질수록 상수의 차이는 의미가 없어지기 때문입니다.
세 가지 표기법
빅 오 표기법 (Big-O Notation) - 최악의 경우 (상한)
- 알고리즘의 최악의 경우 성능을 나타냅니다.
- "아무리 느려도 이 정도는 보장한다"는 의미입니다.
- 실무에서 가장 많이 사용됩니다.
빅 오메가 표기법 (Big-Ω Notation) - 최선의 경우 (하한)
- 알고리즘의 최선의 경우 성능을 나타냅니다.
- "최소한 이 정도의 시간이 필요하다"는 의미입니다.
- 이론적 분석에 주로 사용됩니다.
빅 세타 표기법 (Big-Θ Notation) - 평균적인 경우
- 알고리즘의 평균적인 성능을 나타냅니다.
- 상한과 하한이 같을 때 사용합니다.
- 가장 정확하지만 계산이 복잡합니다.
왜 빅 오 표기법을 주로 사용할까?
실무에서는 알고리즘의 성능 평가 시 거의 항상 빅 오 표기법만을 사용합니다.
이유
- 안전한 설계: 최악의 경우를 대비하면 어떤 상황에서도 성능을 보장할 수 있습니다.
- 간단한 분석: 평균이나 최선의 경우보다 분석이 명확합니다.
- 실용성: 사용자 경험을 위해 "최악의 경우에도 이 정도 성능"을 보장하는 것이 중요합니다.
따라서 앞으로 설명할 모든 내용은 빅 오 표기법을 기준으로 합니다.
빅 오 표기법의 종류와 예제
빅 오 표기법을 성능이 좋은 순서대로 특징과 어떤식으로 사용하고 있는지 실제 사례에 빗대어 알아보겠습니다. 예제 코드는 Java 로 진행하는점 참고부탁드립니다.
O(1) - 상수 시간 (Constant Time)
입력 크기와 관계없이 항상 일정한 시간이 걸립니다. 가장 이상적인 시간 복잡도입니다.
특징
- 데이터가 100개든 100만 개든 실행 시간이 동일합니다.
- 인덱스로 배열 요소에 접근하는 경우
- 해시 테이블에서 키로 값을 찾는 경우 (평균)
실제 사례
- 스택의 Push/Pop 연산
- 큐의 Enqueue/Dequeue 연산 (배열이 아닌 링크드 리스트 구현 시)
- 해시맵의 조회/삽입/삭제 (평균)
에제 코드
public class ConstantTimeExample {
// 배열의 첫 번째 요소 가져오기
public static int getFirstElement(int[] arr) {
return arr[0]; // 항상 한 번의 연산
}
// 스택 Push 연산
public static void stackPush(Stack<Integer> stack, int item) {
stack.push(item); // O(1)
}
// 스택 Pop 연산
public static int stackPop(Stack<Integer> stack) {
return stack.pop(); // O(1)
}
}O(log n) - 로그 시간 (Logarithmic Time)
입력 크기가 증가해도 실행 시간이 천천히 증가합니다. 매우 효율적인 알고리즘입니다.
특징
- 문제를 절반씩 나누어 해결하는 분할 정복 방식에서 나타납니다.
- 입력이 2배 증가해도 연산은 1번만 추가됩니다.
- 데이터가 1,000개에서 1,000,000개로 증가해도 연산은 10번 정도만 증가합니다.
실제 사례
- 이진 탐색 (Binary Search)
- 균형 잡힌 이진 탐색 트리(BST)의 탐색/삽입/삭제
- 특정 자료구조의 연산 (힙의 삽입/삭제)
예제 코드
public class LogarithmicTimeExample {
// 이진 탐색 example
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 오버플로우 방지
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1; // 오른쪽 절반 탐색
} else {
right = mid - 1; // 왼쪽 절반 탐색
}
}
return -1; // 찾지 못함
}
}이진 탐색을 시각적으로 분석해보기
이진 탐색에서 16개 요소를 찾을 경우
16 → 8 → 4 → 2 → 1 (최대 5번)
log₂(16) = 4 (실제로는 최대 5번, 올림)O(n) - 선형 시간 (Linear Time)
입력 크기에 비례하여 실행 시간이 증가합니다. 가장 흔하게 접하는 시간 복잡도입니다.
특징
- 데이터가 2배 증가하면 시간도 2배 증가합니다.
- 모든 요소를 한 번씩 확인해야 하는 경우
- 가장 기본적이고 직관적인 복잡도입니다.
실제 사례
- 배열/리스트 순회
- 선형 탐색
- 배열의 합계/평균 계산
- 리스트에서 특정 값 찾기
예제 코드
public class LinearTimeExample {
// 배열에서 최댓값 찾기
public static int findMax(int[] arr) {
int maxVal = arr[0];
for (int num : arr) { // 모든 요소를 한 번씩 순회
if (num > maxVal) {
maxVal = num;
}
}
return maxVal;
}
// 선형 탐색
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) { // 최악의 경우 모든 요소 확인
if (arr[i] == target) {
return i;
}
}
return -1;
}
}O(n log n) - 선형 로그 시간 (Linearithmic Time)
분할 정복 방식의 정렬 알고리즘에서 주로 나타나는 복잡도입니다. O(n)보다는 느리지만 O(n²)보다는 훨씬 빠릅니다.
특징
- 데이터를 나누고(log n) 각 부분을 처리(n)하는 방식
- 효율적인 정렬 알고리즘의 평균적인 성능
- 대용량 데이터 정렬에 적합합니다.
실제 사례
- 병합 정렬 (Merge Sort)
- 퀵 정렬 (Quick Sort) - 평균
- 힙 정렬 (Heap Sort)
- 대부분의 효율적인 정렬 알고리즘
예제 코드
public class LinearithmicTimeExample {
// 병합 정렬
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
// 분할 (log n 단계)
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 병합 (n 연산)
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
// 임시 배열 생성
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
// 데이터 복사
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
// 병합
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 남은 요소 복사
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
}병합 정렬을 시각적으로 분석해보기
병합 정렬의 분할 과정 (log n):
[8,3,5,2,7,1,4,6]
[8,3,5,2] [7,1,4,6] ← 1단계
[8,3][5,2] [7,1][4,6] ← 2단계
[8][3][5][2] [7][1][4][6] ← 3단계 (log₂8 = 3)
각 단계마다 모든 요소 처리 (n) → O(n log n)O(n²) - 이차 시간 (Quadratic Time)
입력 크기의 제곱에 비례하여 실행 시간이 증가합니다. 중첩 반복문에서 자주 나타납니다.
특징
- 데이터가 2배 증가하면 시간은 4배 증가합니다.
- 중첩된 반복문을 사용하는 경우
- 소규모 데이터에는 괜찮지만 대용량 데이터에는 비효율적입니다.
실제 사례
- 버블 정렬 (Bubble Sort)
- 선택 정렬 (Selection Sort)
- 삽입 정렬 (Insertion Sort)
- 이중 반복문을 사용한 알고리즘
예제 코드
public class QuadraticTimeExample {
// 버블 정렬
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) { // 외부 루프: n번
for (int j = 0; j < n - i - 1; j++) { // 내부 루프: n번
if (arr[j] > arr[j + 1]) {
// swap
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 중복 찾기
public static List<Integer> findDuplicates(int[] arr) {
List<Integer> duplicates = new ArrayList<>();
for (int i = 0; i < arr.length; i++) { // n번
for (int j = i + 1; j < arr.length; j++) { // n번
if (arr[i] == arr[j] && !duplicates.contains(arr[i])) {
duplicates.add(arr[i]);
}
}
}
return duplicates;
}
}성능 비교
n = 10: -> 100번 연산
n = 100: -> 10,000번 연산
n = 1,000: -> 1,000,000번 연산O(2ⁿ) - 지수 시간 (Exponential Time)
입력이 1씩 증가할 때마다 실행 시간이 2배씩 증가합니다. 매우 비효율적인 알고리즘입니다.
특징
- 재귀 호출이 2번씩 발생하는 경우
- 데이터가 조금만 커져도 실행 시간이 기하급수적으로 증가합니다.
- 실용적이지 않으며, 동적 프로그래밍 등으로 최적화가 필요합니다.
실제사례
- 최적화되지 않은 피보나치 수열
- 부분집합의 모든 조합 생성
- 하노이의 탑 문제
- 브루트 포스(완전 탐색) 알고리즘
예제 코드
public class ExponentialTimeExample {
// 재귀를 이용한 피보나치 (비효율적)
public static int fibonacciRecursive(int n) {
if (n <= 1) {
return n;
}
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
// 각 호출마다 2개의 재귀 호출 발생
}
}피보나치 수열을 시각적으로 분석해보기
fibonacci(5) 호출 트리:
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) ... ... ...
높이: n, 각 레벨마다 노드 2배 증가 → O(2ⁿ)성능 비교
n = 5: -> 32번 연산
n = 10: -> 1,024번 연산
n = 20: -> 1,048,576번 연산
n = 30: -> 1,073,741,824번 연산 (10억 번!)피보나치 수열 최적화 예제 코드
public class FibonacciOptimized {
// 동적 프로그래밍으로 O(n)으로 개선
public static int fibonacciDP(int n) {
if (n <= 1) {
return n;
}
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// 공간 복잡도를 O(1)로 더 최적화
public static int fibonacciOptimized(int n) {
if (n <= 1) {
return n;
}
int prev2 = 0;
int prev1 = 1;
int current = 0;
for (int i = 2; i <= n; i++) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return current;
}
}빅 오 표기법 성능 비교
시간 복잡도를 그래프로 비교하면 아래 이미지와 같습니다
작은 데이터(n=10)에서의 연산 횟수 비교
- O(1): 1번
- O(log n): ~3번
- O(n): 10번
- O(n log n): ~33번
- O(n²): 100번
- O(2ⁿ): 1,024번
큰 데이터(n=1,000)에서의 연산 횟수 비교
- O(1): 1번
- O(log n): ~10번
- O(n): 1,000번
- O(n log n): ~10,000번
- O(n²): 1,000,000번
- O(2ⁿ): 계산 불가능 (우주의 원자 수보다 많음)
예제) 알고리즘 비교 연습
같은 문제를 다른 시간 복잡도로 해결하는 예제를 통해 어떤식으로 비교해야하는지 살펴보겠습니다.
예제: 배열에서 두 수의 합이 target이 되는 인덱스 찾기
방법 1: 이중 반복문 - O(n²)
public class TwoSumBruteForce {
public static int[] twoSum(int[] nums, int target) {
// 모든 조합 확인
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[]{};
}
}방법 2: 해시맵 사용 - O(n)
public class TwoSumOptimized {
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[]{};
}
}성능 비교
- 입력 크기 100: O(n²)는 10,000번 연산, O(n)은 100번 연산
- 입력 크기 10,000: O(n²)는 100,000,000번 연산, O(n)은 10,000번 연산
예제) 빅 오 표기법 분석 연습
코드를 보고 시간 복잡도를 판단하는 연습을 해봅시다.
예제 1
public void example1(int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += i;
}
System.out.println(sum);
}답: O(n) - 반복문이 n번 실행됩니다.
예제 2
public void example2(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println(i + j);
}
}
}답: O(n²) - 중첩된 반복문이 각각 n번씩 실행됩니다.
예제 3
public void example3(int n) {
for (int i = 1; i < n; i *= 2) {
System.out.println(i);
}
}답: O(log n) - i가 2배씩 증가하므로 로그 시간입니다.
예제 4
public void example4(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j *= 2) {
System.out.println(i + j);
}
}
}답: O(n log n) - 외부 반복문 O(n), 내부 반복문 O(log n)
예제 5
public void example5(int[] arr) {
int n = arr.length;
Arrays.sort(arr); // O(n log n)
for (int i = 0; i < n; i++) { // O(n)
System.out.println(arr[i]);
}
}답: O(n log n) - 정렬이 지배적인 연산입니다. O(n log n) + O(n) = O(n log n)
복잡도 판단 시 check point
반복문 확인
- 단일 반복문: O(n)
- 이중 반복문: O(n²)
- 삼중 반복문: O(n³)
반복문 내부의 증가 방식 확인
i++: 선형 증가 → O(n)i *= 2또는i /= 2: 로그 증가/감소 → O(log n)
재귀 함수 분석
- 재귀 호출 횟수와 각 호출의 작업량을 곱합니다.
- 이진 트리 형태의 재귀: O(2ⁿ)
- 분할 정복 재귀: O(log n) 또는 O(n log n)
여러 연산이 순차적으로 있을 경우
- 가장 큰 복잡도가 전체 복잡도가 됩니다.
- O(n) + O(n²) + O(log n) = O(n²)
Java 컬렉션의 시간 복잡도
ArrayList
- get(index): O(1)
- add(element): O(1) 평균, O(n) 최악 (재할당 발생 시)
- remove(index): O(n)
- contains(element): O(n)
LinkedList
- get(index): O(n)
- add(element): O(1)
- remove(index): O(n)
- contains(element): O(n)
HashMap
- get(key): O(1) 평균
- put(key, value): O(1) 평균
- remove(key): O(1) 평균
- containsKey(key): O(1) 평균
TreeMap
- get(key): O(log n)
- put(key, value): O(log n)
- remove(key): O(log n)
HashSet
- add(element): O(1) 평균
- contains(element): O(1) 평균
- remove(element): O(1) 평균
언제 최적화를 고려 해야할까?
최적화가 필요한 경우
- 대용량 데이터 처리 (n > 10,000)
- 실시간 응답이 중요한 서비스
- 반복적으로 자주 호출되는 함수
- O(n²) 이상의 알고리즘을 사용할 때
최적화가 불필요한 경우
- 소규모 데이터 (n < 100)
- 한 번만 실행되는 초기화 코드
- 가독성이 성능보다 중요한 경우
최적화 시 고려해야할 점
항상 최악의 경우를 고려 하기
// 평균 O(1)이지만 최악 O(n)인 HashMap
HashMap<String, Integer> map = new HashMap<>();
// 해시 충돌이 많으면 성능 저하..불필요한 중첩 반복문 피하기
// 나쁜 예: O(n²)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i] == arr[j]) {
// ...
}
}
}
// 좋은 예: O(n)
Set<Integer> set = new HashSet<>();
for (int num : arr) {
if (set.contains(num)) {
// ...
}
set.add(num);
}정렬된 데이터는 이진 탐색을 활용하기
// O(n) 선형 탐색
for (int num : sortedArray) {
if (num == target) return true;
}
// O(log n) 이진 탐색
int index = Arrays.binarySearch(sortedArray, target);
return index >= 0;캐싱 활용하기
// 반복 계산을 피하기 위한 메모이제이션
Map<Integer, Integer> memo = new HashMap<>();
public int fibonacci(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) {
return memo.get(n); // O(1)
}
int result = fibonacci(n - 1) + fibonacci(n - 2);
memo.put(n, result);
return result;
}마치며
빅 오 표기법은 알고리즘의 효율성을 평가하는 가장 중요한 도구입니다. 처음에는 저도 장황하고 복잡하게 느껴졌지만, 코드를 작성하고 분석하는 연습을 반복하다 보니 자연스럽게 이해되면서 체득하게 된 것 같습니다.
알고리즘 문제를 풀 때는 항상 "이 코드의 시간 복잡도는 무엇일까?"를 생각하는 습관을 들이는 것이 좋다고합니다. 좋은 알고리즘을 작성하는 길이라 생각하고 저도 실천하려고 합니다.
다음 포스팅에서는 실전 알고리즘 문제를 직접 풀이 해보면서, 빅 오 표기법으로 분석하고 최적화하는 방법을 다뤄보겠습니다!
ref
'CS > 알고리즘' 카테고리의 다른 글
| [알고리즘] 이진 탐색 (Binary Search) (0) | 2025.10.24 |
|---|---|
| [알고리즘] 정렬 알고리즘(선택, 삽입, 버블, 합병, 퀵, 힙) (0) | 2025.10.21 |