[코테 개념 정리] Time Complexity : 시간 복잡도와 Big-O 표기법
2025. 9. 2. 18:12ㆍCS&알고리즘/코테 개념 정리
코딩 테스트 문제를 풀다 보면 빠지지 않고 등장하는 개념이 바로 시간 복잡도입니다.
이번 글에서는 시간 복잡도가 무엇인지, 어떤 종류가 있는지, 그리고 실제 코드에서는 어떻게 표현되는지를 살펴보겠습니다.
이를 이해하기 위해 먼저 연산 횟수와 Big-O 표기법을 알아본 뒤,
시간 복잡도의 종류와 예제 코드를 통해 구체적으로 정리해보겠습니다.
📌 연산 횟수란?
- 알고리즘을 실행할 때 수행되는 기본 연산의 개수
- 실제 컴퓨터가 처리하는 “한 단계 동작(step)”을 단순화해서 센 것
- 초 단위로 시간 측정을 하면 컴퓨터 성능/환경에 따라 달라지므로,
기본 연산 횟수를 세어야 “입력 크기 n에 따른 실행 증가율”을 객관적으로 비교할 수 있음 - 시간 복잡도는 이 연산 횟수를 단순화해서 “증가율(Big-O)”로 표현한 것
기본 연산의 종류
연산 횟수는 다음과 같은 동작이 한 번 일어날 때마다 +1 증가
- 대입 연산: x = 10, currentMax = arr[i]
- 산술 연산: i + 1, a * b
- 비교 연산: if (x < y), i < n
- 논리 연산: &&, ||
- 반복문 제어: for, while의 조건 검사 & 루프 실행
- 함수 호출/리턴: func(), return value
- 조건 분기: if, else → 조건 평가 시
// 배열에서 최댓값 찾기 - O(n)
public class FindMax {
public static int findMax(int[] arr) {
int currentMax = arr[0]; // 대입 1회
for (int i = 1; i < arr.length; i++) { // 반복 조건 검사 (n-1회)
if (arr[i] > currentMax) { // 비교 (n-1회)
currentMax = arr[i]; // 대입 (최악의 경우 n-1회)
}
}
return currentMax;
}
public static void main(String[] args) {
int[] arr = {3, -1, 9, 2, 12};
System.out.println(findMax(arr)); // 12
}
}# 배열에서 최댓값 찾기 - O(n)
def find_max(arr):
current_max = arr[0] # 대입 1회
for i in range(1, len(arr)): # 반복 조건 검사 (n-1회)
if arr[i] > current_max: # 비교 (n-1회)
current_max = arr[i] # 대입 (최악의 경우 n-1회)
return current_max
arr = [3, -1, 9, 2, 12]
print(find_max(arr)) # 12
📌 Big-O 표기법이란?
- 시간 복잡도를 표현하는 표기법
- 알고리즘의 실제 연산 횟수를 n에 대한 증가율로 단순화해서 표현
- 입력 크기 n이 무한히 커질 때의 성능을 평가
- Big-O 외의 표기법이 있지만 코딩 테스트에서는 거의 항상 Big-O 를 기준으로 설명
- Big-O (O): 최악의 경우 (Upper Bound, 가장 많이 걸릴 때)
- Big-Ω (Ω): 최선의 경우 (Lower Bound, 가장 적게 걸릴 때)
- Big-Θ (Θ): 평균/정확한 경계 (Tight Bound)
연산 횟수 단순화 과정
// 배열에서 최댓값 찾기 - O(n)
public class FindMax {
public static int findMax(int[] arr) {
int currentMax = arr[0]; // (1) 초기 대입
for (int i = 1; i < arr.length; i++) { // (2) 반복문 검사
if (arr[i] > currentMax) { // (3) 비교 연산
currentMax = arr[i]; // (4) 대입 (최악의 경우 실행)
}
}
return currentMax;
}
public static void main(String[] args) {
int[] arr = {3, -1, 9, 2, 12};
System.out.println(findMax(arr)); // 12
}
}
연산 횟수
| 연산 | 코드 실행 | 횟수 |
| 초기 대입 | int currentMax = arr[0]; | 1 |
| 반복문 검사 | for (int i = 1; i < arr.length; i++) | (n-1) |
| 비교 연산 | if (arr[i] > currentMax) | (n-1) |
| 대입(worst case) | currentMax = arr[i]; | (n-1) |
| 합계 | 3n - 2 |
단순화 흐름
T(n) = 3n - 2
↓ (상수항 -2 무시)
T(n) ≈ 3n
↓ (상수 계수 3 무시)
T(n) ≈ n
↓
시간 복잡도 = O(n)
📌 시간 복잡도 : Time Complexity
- 알고리즘 실행 시간을 입력 크기 n과의 관계로 표현한 것
- 실제 초 단위가 아닌 연산 횟수의 증가율을 표현
- Big-O 표기법으로 표현
📊 시간 복잡도 차트 이미지로 보기
시간 복잡도 종류
효율성 : O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
아래로 갈수록 실행 속도가 느려짐
| 시간 복잡도 | 이름 | 예시 |
| O(1) | 상수 시간 | 배열 인덱스 접근 해시 테이블 조회/ 삽입 변수 값 대입 스택/큐 push&pop |
| O(log n) | 로그 시간 | 이진 탐색 |
| O(n) | 선형 시간 | 배열 전체 탐색 |
| O(n log n) | 로그 선형 | 퀵/병합/힙 정렬 |
| O(n²) | 이차 시간 | 이중 반복문, 버블 정렬 |
| O(2ⁿ) | 지수 시간 | 부분집합 탐색 순열/조합 탐색(백트래킹) 단순 재귀 피보나치 |
| O(n!) | 팩토리얼 시간 | 순열 탐색 |
👀 코드로 알아보기
O(1) - 상수 시간
- 단 하나의 연산
- 입력 크기와 상관없이 항상 일정한 실행 횟수
// Java
// 배열 인덱스 접근
int[] arr = {10, 20, 30, 40, 50};
int value = arr[3];
// 해시맵/딕셔너리 조회
Map<String, Integer> map = new HashMap<>();
map.put("apple", 3);
int value = map.get("apple"); // 평균 O(1)
// 변수 값 변경
int x = 10;
x = x + 5; // O(1)
// 스택/큐 push & pop (배열 기반 구현일 경우)
Stack<Integer> stack = new Stack<>();
stack.push(10); // O(1)
stack.pop(); // O(1)# Python
# 배열(리스트) 인덱스 접근
arr = [10, 20, 30, 40, 50]
value = arr[3] # O(1)
# 딕셔너리 조회
d = {"apple": 3, "banana": 5}
v1 = d["apple"] # 평균 O(1)
# 변수 값 변경
x = 10
x = x + 5 # O(1)
# 스택 push & pop (리스트 사용)
stack = []
stack.append(10) # O(1)
stack.pop() # O(1)
O(log n) - 로그 시간
- 입력 크기가 커져도 실행 횟수는 조금씩만 증가
- 알고리즘에서 log n은 탐색 범위가 절반씩 줄어드는 경우
// Java
// (1) 이진 탐색 - 정렬된 배열에서 값 찾기
int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// (2) 숫자 나누기 반복 - n을 2로 계속 나누는 과정
int divideByTwo(int n) {
int count = 0;
while (n > 1) {
n = n / 2; // 매번 절반으로 줄어듦
count++;
}
return count; // 반복 횟수 = O(log n)
}# Python
# (1) 이진 탐색 - 정렬된 배열에서 값 찾기
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# (2) 숫자 나누기 반복 - n을 2로 계속 나누는 과정
def divide_by_two(n):
count = 0
while n > 1:
n = n // 2 # 매번 절반으로 줄어듦
count += 1
return count # 반복 횟수 = O(log n)
O(n) - 선형 시간
- 입력 크기 n에 비례해서 실행 횟수가 늘어남
// Java
// (1) 배열 전체 출력
void printAll(int[] arr) {
for (int num : arr) { // n번 반복
System.out.println(num);
}
}
// (2) 배열에서 특정 값 찾기 (선형 탐색)
int findTarget(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) { // n번 반복
if (arr[i] == target) return i;
}
return -1; // 못 찾으면 -1
}# Python
# (1) 배열 전체 출력
def print_all(arr):
for num in arr: # n번 반복
print(num)
# (2) 배열에서 특정 값 찾기 (선형 탐색)
def find_target(arr, target):
for i, num in enumerate(arr): # n번 반복
if num == target:
return i
return -1 # 못 찾으면 -1
O(n log n) - 로그 선형 시간
- 입력 데이터 n개 각각이 log n 단계의 연산을 수행하는 경우
- 단순 정렬보다 빠르고, n² 정렬보다는 훨씬 효율적
- 대규모 데이터 정렬 시 자주 사용
// Java
import java.util.*;
// (1) 배열 정렬 (퀵/병합/힙 정렬 기반)
int[] arr = {5, 2, 9, 1, 5, 6};
Arrays.sort(arr); // 평균 O(n log n)
// (2) 힙(우선순위 큐) 사용
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5); // O(log n)
pq.add(2); // O(log n)
pq.add(9); // O(log n)
while (!pq.isEmpty()) {
System.out.println(pq.poll()); // n번 poll → 전체 O(n log n)
}# Python
# (1) 배열 정렬 (TimSort: O(n log n))
arr = [5, 2, 9, 1, 5, 6]
arr.sort() # 평균 O(n log n)
# (2) 힙(우선순위 큐) 사용
import heapq
pq = []
heapq.heappush(pq, 5) # O(log n)
heapq.heappush(pq, 2) # O(log n)
heapq.heappush(pq, 9) # O(log n)
while pq:
print(heapq.heappop(pq)) # n번 pop → 전체 O(n log n)
O(n²) - 이차 시간
- 중첩 반복문, 입력 크기가 커질수록 급격히 증가
- 입력 크기가 2배 -> 실행 횟수는 4배 증가, 입력 크기가 10배 -> 실행 횟수는 100배 증가
- 보통 n ≤ 10³ 정도까지는 가능하지만, n = 10⁵ 이상이면 사실상 불가능
// Java
// (1) 모든 쌍 출력
void printPairs(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.println(arr[i] + ", " + arr[j]); // n * n번 실행
}
}
}
// (2) 버블 정렬
void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}# Python
# (1) 모든 쌍 출력
def print_pairs(arr):
for i in arr:
for j in arr:
print(i, j) # n * n번 실행
# (2) 버블 정렬
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
O(2ⁿ) - 지수 시간
- 입력 크기 n이 늘어날 때, 실행 횟수가 2ⁿ에 비례
- 입력 크기가 조금만 커져도 연산 횟수가 폭발적으로 증가
// Java
// (1) 부분집합 생성 (Power Set)
void generateSubsets(int[] arr, int index, List<Integer> current) {
if (index == arr.length) {
System.out.println(current);
return;
}
// 원소 포함 X
generateSubsets(arr, index + 1, new ArrayList<>(current));
// 원소 포함 O
current.add(arr[index]);
generateSubsets(arr, index + 1, new ArrayList<>(current));
}
// (2) 피보나치 수열 (재귀, 최악의 경우 O(2^n))
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}# Python
# (1) 부분집합 생성 (Power Set)
def generate_subsets(arr, index=0, current=None):
if current is None:
current = []
if index == len(arr):
print(current)
return
# 원소 포함 X
generate_subsets(arr, index + 1, current[:])
# 원소 포함 O
generate_subsets(arr, index + 1, current + [arr[index]])
# (2) 피보나치 수열 (재귀, 최악의 경우 O(2^n))
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
O(n!) - 팩토리얼 시간
- 모든 순열 탐색에서 대표적으로 발생
- 입력 크기 n이 늘어날 때, 실행 횟수가 n! (n × (n-1) × (n-2) … × 1)에 비례
- 데이터 크기가 조금만 커져도 현실적으로 불가능 → 보통 n ≤ 10 이하에서만 실험 가능
- n = 5 → 120가지 경우
- n = 10 → 3,628,800가지 경우
- n = 15 → 약 1조 3천억 가지 경우 → 현실적으로 불가능
// Java
import java.util.*;
public class Permutations {
public static void main(String[] args) {
int[] arr = {1, 2, 3};
permute(arr, 0);
}
static void permute(int[] arr, int start) {
if (start == arr.length) {
System.out.println(Arrays.toString(arr));
return;
}
for (int i = start; i < arr.length; i++) {
swap(arr, start, i);
permute(arr, start + 1); // 재귀 호출 → n! 경우 탐색
swap(arr, start, i); // 원상복구 (백트래킹)
}
}
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}# Python
# (1) itertools 활용
from itertools import permutations
arr = [1, 2, 3]
for p in permutations(arr):
print(p) # 3! = 6가지 경우
# (2) 재귀로 직접 구현
def permute(arr, current=[]):
if not arr:
print(current)
return
for i in range(len(arr)):
permute(arr[:i] + arr[i+1:], current + [arr[i]]) # n! 경우 탐색
permute([1, 2, 3])
참고 영상
https://www.youtube.com/watch?v=ysn9dLDNLEU&list=PLetkvXWioaD18_Hp3LTy0RQ1tylkE44RS&index=2
'CS&알고리즘 > 코테 개념 정리' 카테고리의 다른 글
| [코테 개념 정리] 자료구조와 복잡도 (0) | 2025.09.04 |
|---|---|
| [코테 개념 정리] Space Complexity : 공간 복잡도 (0) | 2025.09.04 |