시간 복잡도 (Time Complexity) / 공간 복잡도 (Space Complexity)

⏰ 시간 복잡도 (Time Complexity)

• 입력 크기 n이 증가할 때, 연산 횟수가 얼마나 증가하는 지를 나타낸 지표
• 연산 횟수 증가 비율을 나타내는 수치이며, 보통 Big-O 표기법 사용

💡 Big-O 표기법
    - 최악의 경우 기준으로 증가 속도를 표현하는 방식
    - 상수는 무시

 

 

[EX.Big-O]

O(1)
O(n)
O(n^2)
O(log n)
O(n log n)

// 상수는 무시
3n + 5 → O(n)
5n^2 + 10n + 1 → O(n^2)

 

---

✔️ 시간 복잡도 성능 비교

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

 

 

[Big-O Complexity]

 

---

✔️ 계산 방법

🔹n번 실행 : O(n)

• 반복문 횟수만큼 실행
• 여러 개의 독립 루프도 여기에 해당 (ex. n+n+n → 3n → 상수는 무시되므로 결과는 O(n))
• 단순 재귀 (n번 호출)

// n번 실행
for (int i = 0; i < n; i++) {
    System.out.println(i);
}

// 독립 루프는 더하기(지만 상수는 무시)
for (int i = 0; i < n; i++) { }
for (int i = 0; i < n; i++) { }

// 재귀
void dfs(int n) {
    if (n == 0) return;
    dfs(n - 1);
}

 

 

🔹중첩 반복문 : O(n²)

• 반복문 내부에서 반복문을 사용하는 경우 (n*n)

// n*n번 실행(반복문 중첩)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + j);
    }
}

 

 

🔹반씩 줄어드는 경우 : O(log n)

• n → n / 2 → n / 4 → log²n  → O(log n)
• ex. 이진 탐색

// 반씩 줄어드는 경우
while (n > 1) {
    n = n / 2;
}

 

 

🔹여러 갈래로 나뉘는 재귀 : O(m^n)

• ex. 두 갈래로 뻗는 재귀가 n번 실행되는 경우 → 2² -> O(2^n)

// 여러 갈래로 뻗어가는 재귀
void f(int n) {
    if (n == 0) return;
    f(n - 1);
    f(n - 1);
}

 

 

---

✔️ 관련 알고리즘 및 자료구조

 

시간 복잡도	자료구조/알고리즘
O(1)	HashMap / HashSet 접근, 배열 index 접근, Stack push / pop, Queue enqueue / dequeue
O(log n)	Binary Search, Heap insert / delete, Tree 탐색
O(n)	배열 순회, 선형 탐색, BFS / DFS, Counting
O(n log n)	Merge Sort, Quick Sort, Heap Sort,
O(n²)	Bubble Sort, Selection Sort, Insertion sort, Floyd-Warshall
O(2ⁿ)	DFS 완전 탐색, Backtracking, 부분 집합
O(n!)	Permutation, Traveling Salesman (brute force)

 

 

 

---

🛖 공간 복잡도 (Space Complexity)

• 알고리즘이 실행될 때 사용하는 메모리의 양
• 입력 데이터 크기 n이 커질 때 프로그램이 메모리를 어느 정도 사용하는 지를 나타내는 지표

---

✔️ 공간 복잡도의 구성

1️⃣ 입력 데이터 자체가 차지하는 공간

• 입력으로 주어진 배열, 문자열 등
• 일반적으로 공간 복잡도 계산에서는 제외

 

2️⃣ 알고리즘이 추가로 차지하는 공간 ✨

• 입력 데이터 외 알고리즘이 실행하면서 새로 사용하는 메모리
• ex. 변수, 각종 자료구조, 재귀 스택, 보조 배열 등

 

[EX.공간 복잡도의 구성]

int[] arr = new int[n];

int sum = 0;
for(int i=0;i<n;i++){
    sum += arr[i];
}

arr    // 1) 입력 데이터
sum, i  // 2) 알고리즘이 추가로 사용한 공간

 

 

---

✔️ 공간 복잡도 예시

🔹 O(1) 공간 (Constant Space)

• 입력 크기와 상관없이 항상 같은 메모리

[EX. O(1)]

int sum = 0;

for(int i=0;i<n;i++){
    sum += arr[i];
}

 

▶️ 사용 메모리

sum
i

 

 

🔹 O(n) 공간

• 입력 크기만큼 메모리를 추가로 사용
• 재귀의 경우 Stack 메모리를 사용하며, 재귀의 깊이가 n인 경우 공간복잡도는 O(n)
  → 재귀의 깊이가 너무 깊으면 StackOverflow 발생

[EX. O(n)]

int[] copy = new int[n];

for(int i=0;i<n;i++){
    copy[i] = arr[i];
}

// 재귀
void dfs(int n){
    if(n==0) return;
    dfs(n-1);
}

 

▶️ 사용 메모리

copy[n]

// 재귀
dfs(n)
dfs(n-1)
dfs(n-2)
→ stack에 쌓임

 

 

🔹 O(n²) 공간

• 입력 크기의 제곱만큼 메모리 추가 사용

[EX. O(n²)]

int[][] matrix = new int[n][n];

 

▶️ 사용 메모리

n * n

 

 

 

---

✔️ 정리

 

공간	의미
O(1)	변수 몇 개, 두 변수 swap, In-place 정렬(선택 정렬, 힙 정렬), 이진 탐색(반복문), Two-pointer 알고리즘
O(log n)	재귀 call stack (이진 탐색, 퀵 정렬)
O(n)	BFS / DFS, 배열 복사
O(n log n)	트리 구조
O(n²)	2차원 배열, Floyd-Warshall DP
O(2ⁿ)	subset 저장, memoization
O(!)	permutation, 모든 순열 리스트 저장