# 시간, 공간 복잡도의 개념과 빅오 표기법 ## 1. 왜 복잡도를 배워야 할까? 프로그램을 작성할 때 "이 코드가 얼마나 빠를까?", "메모리를 얼마나 사용할까?"를 알아야 합니다. 복잡도는 이를 수학적으로 표현하는 방법입니다. ### 실생활 비유 - 책에서 특정 페이지 찾기: - **방법 1**: 처음부터 한 장씩 넘기기 → 느림 - **방법 2**: 페이지 번호를 보고 바로 가기 → 빠름 이 차이를 정확히 표현하는 것이 바로 **복잡도**입니다! --- ## 2. 시간복잡도 (Time Complexity) **정의**: 알고리즘이 실행되는 데 걸리는 시간을 입력 크기(n)에 따라 표현한 것 ### 기본 예제로 이해하기 > **시간복잡도: O(n)** > ```cpp // 예제 1: 배열에서 특정 값 찾기 void findValue(int arr[], int n, int target) { for(int i = 0; i < n; i++) { if(arr[i] == target) { cout << "찾았다!" << endl; return; } } } ``` - 배열에 10개 요소 → 최대 10번 확인 - 배열에 100개 요소 → 최대 100번 확인 - 배열에 n개 요소 → 최대 n번 확인 --- > **시간복잡도: O(1)** - 상수 시간 > ```cpp // 예제 2: 배열의 첫 번째 값 가져오기 int getFirst(int arr[]) { return arr[0]; } ``` - 배열 크기와 상관없이 항상 1번만 실행 --- > **시간복잡도: O(n²)** > ```cpp // 예제 3: 이중 반복문 void printPairs(int arr[], int n) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cout << arr[i] << ", " << arr[j] << endl; } } } ``` - 바깥 반복문: n번 - 안쪽 반복문: 각각 n번 - 총 실행 횟수: n × n = n² --- ## 3. 빅오 표기법 (Big-O Notation) **빅오는 알고리즘의 최악의 경우 성능을 나타냅니다.** ### 왜 "최악의 경우"일까? ```cpp void search(int arr[], int n, int target) { for(int i = 0; i < n; i++) { if(arr[i] == target) return; } } // n 대신, arr.size() 이용 ``` - **최선의 경우**: 첫 번째 요소가 target → 1번 실행 - **평균의 경우**: 중간쯤 → n/2번 실행 - **최악의 경우**: 끝에 있거나 없음 → n번 실행 빅오는 최악의 경우(n번)를 기준으로 합니다. 왜냐하면 알고리즘의 **성능 보장**을 해야 하기 때문입니다. ### 빅오 표기법의 규칙 ### 규칙 1: 상수는 무시 ```cpp void example(int n) { int x = 5 + 5; // 2번 연산 cout << x << endl; // 1번 연산 for(int i = 0; i < n; i++) { cout << i << endl; // n번 연산 } } // 총: 3 + n번 // 하지만 빅오: O(n) ``` n이 커지면 상수(3)는 의미가 없어집니다: - n = 100: 103번 → 거의 100 - n = 1,000,000: 1,000,003번 → 거의 1,000,000 ### 규칙 2: 가장 큰 항만 남김 ```cpp void example(int n) { for(int i = 0; i < n; i++) { // n번 cout << i << endl; } for(int i = 0; i < n; i++) { // n번 for(int j = 0; j < n; j++) { // n번 cout << i << j << endl; } } } // 총: n + n² 번 // 하지만 빅오: O(n²) ``` n이 커지면 n²이 n을 압도합니다: - n = 10: 10 + 100 = 110 → n²이 대부분 - n = 1000: 1,000 + 1,000,000 = 1,001,000 → n²이 거의 전부 ### 규칙 3: 계수는 무시 ```cpp // 5n번 실행되어도 O(n) // 3n²번 실행되어도 O(n²) ``` --- ## 4. 주요 시간복잡도 비교 ### O(1) - 상수 시간 **"입력 크기와 무관하게 항상 일정"** ```cpp int getElement(int arr[], int index) { return arr[index]; // 배열 접근: 항상 한 번 } int first = arr[0]; // O(1) int last = arr[n-1]; // O(1) ``` **실생활 비유**: 엘리베이터에서 버튼 누르기 - 어느 층이든 버튼 한 번 --- ### O(log n) - 로그 시간 **"문제를 반씩 나누면서 해결"** ```cpp // 이진 탐색 (정렬된 배열에서) == 이분 탐색 int binarySearch(int arr[], int n, int target) { int left = 0, right = n - 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; } ``` **동작 과정** (배열 크기 16): 1. 16개 확인 → 8개로 줄임 2. 8개 확인 → 4개로 줄임 3. 4개 확인 → 2개로 줄임 4. 2개 확인 → 1개로 줄임 - 총 4번 (log₂16 = 4) **실생활 비유**: 전화번호부에서 이름 찾기 - 중간을 펴서 앞/뒤 결정 - 다시 중간을 펴서 앞/뒤 결정 - 반복... --- ### O(n) - 선형 시간 **"모든 요소를 한 번씩 확인"** ```cpp int sum(int arr[], int n) { int total = 0; for(int i = 0; i < n; i++) { total += arr[i]; } return total; } // => sum = n*(n+1)/2; --> O(1) ``` - 10개 → 10번 - 100개 → 100번 - n개 → n번 **실생활 비유**: 줄 서 있는 사람 수 세기 - 한 명씩 세야 함 --- ### O(n log n) - 선형 로그 시간 → O(n^2)보다는 작음 O(n)보다는 큼 **"효율적인 정렬"** ```cpp // 병합 정렬, 퀵 정렬 등 sort(arr, arr + n); // C++ STL의 sort ``` - 문제를 나누고(log n) 각 단계에서 모든 요소 처리(n) - n × log n **실생활 비유**: 카드 더미를 여러 개로 나눠서 각각 정렬 후 합치기 --- ### O(n²) - 제곱 시간 **"이중 반복문"** ```cpp // 버블 정렬 void bubbleSort(int arr[], int n) { for(int i = 0; i < n; i++) { for(int j = 0; j < n-1; j++) { if(arr[j] > arr[j+1]) { swap(arr[j], arr[j+1]); } } } } ``` - 10개 → 100번 - 100개 → 10,000번 - 1000개 → 1,000,000번 **실생활 비유**: 반 학생들끼리 서로 악수하기 - 모든 쌍의 조합 --- ### O(2ⁿ) - 지수 시간 **"매우 느림! 가능한 모든 조합" - 피보나치 수열** ```cpp // 피보나치 (비효율적 방법) int fib(int n) { if(n <= 1) return n; return fib(n-1) + fib(n-2); // 2개로 분기 } ``` - n = 5 → 31번 - n = 10 → 1,023번 - n = 20 → 1,048,575번 **실생활 비유**: 체스에서 모든 가능한 수 계산 --- ### O(n!) - 팩토리얼 시간 **"최악! 거의 사용 불가"** ```cpp // 모든 순열 생성 void permute(int arr[], int n) { // n개 요소의 모든 순서 나열 // n! 가지 } ``` - 5개 → 120가지 - 10개 → 3,628,800가지 - 15개 → 1,307,674,368,000가지 --- ## 5. 속도 비교 (n=100일 때) ``` O(1) = 1번 O(log n) = 7번 (log₂100 ≈ 7) -> 100 50 25 12 6 3 1 O(n) = 100번 O(n log n)= 700번 -> logn(7) * n(100) O(n²) = 10,000번 O(2ⁿ) = 1,267,650,600,228,229,401,496,703,205,376번 (거의 불가능) O(n!) = 너무 커서 계산 불가 ``` ### 시각적 그래프 ``` 실행 시간 | | O(n!) | O(2ⁿ) | O(n²) | O(n log n) | O(n) | O(log n) |________O(1)________________________ 입력 크기(n) ``` --- ## 6. 공간복잡도 (Space Complexity) **정의**: 알고리즘이 실행되는 데 필요한 메모리 양을 입력 크기에 따라 표현한 것 ### O(1) - 상수 공간 ```cpp int sum(int arr[], int n) { int total = 0; // 변수 1개 for(int i = 0; i < n; i++) { total += arr[i]; } return total; } // 공간복잡도: O(1) // total 변수 하나만 추가로 사용 ``` ### O(n) - 선형 공간 ```cpp vector copyArray(int arr[], int n) { vector newArr(n); // n개 크기의 새 배열 for(int i = 0; i < n; i++) { newArr[i] = arr[i]; } return newArr; } // 공간복잡도: O(n) // n개 요소를 저장하는 배열 생성 ``` ### O(n²) - 제곱 공간 ```cpp void create2DArray(int n) { int arr[n][n]; // n×n 크기의 2차원 배열 } // 공간복잡도: O(n²) ``` ### 재귀 호출의 공간복잡도 ```cpp int factorial(int n) { if(n <= 1) return 1; return n * factorial(n-1); } // 공간복잡도: O(n) // 재귀 호출 스택이 n개 쌓임 ``` ## 7. 실전 예제로 복잡도 분석하기 ### 예제 1: 단순 탐색 ```cpp bool contains(int arr[], int n, int target) { for(int i = 0; i < n; i++) { if(arr[i] == target) return true; } return false; } // 시간: O(n) - 최악의 경우 모든 요소 확인 // 공간: O(1) - 추가 메모리 사용 없음 ``` ### 예제 2: 중복 찾기 ```cpp bool hasDuplicate(int arr[], int n) { for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { if(arr[i] == arr[j]) return true; } } return false; } // 시간: O(n²) - 이중 반복문 // 공간: O(1) - 추가 메모리 사용 없음 ``` ### 예제 3: 더 효율적인 중복 찾기 ```cpp bool hasDuplicate(int arr[], int n) { unordered_set seen; for(int i = 0; i < n; i++) { if(seen.count(arr[i])) return true; seen.insert(arr[i]); } return false; } // 시간: O(n) - 한 번만 순회 // 공간: O(n) - set에 최대 n개 저장 ``` **Trade-off**: 메모리를 더 사용해서 시간을 절약! ### 예제 4: 복잡한 함수 분석 ```cpp void complexFunction(int arr[], int n) { // 부분 1 for(int i = 0; i < n; i++) { cout << arr[i]; } // 부분 2 for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cout << arr[i] + arr[j]; } } // 부분 3 sort(arr, arr + n); } // 시간복잡도 분석: // 부분 1: O(n) // 부분 2: O(n²) // 부분 3: O(n log n) // 전체: O(n) + O(n²) + O(n log n) = O(n²) // 가장 큰 항만 남김! ``` ## 8. 복잡도 개선하기 ### 문제: 배열에서 두 수의 합이 target인 쌍 찾기 **방법 1: 무식하게** ```cpp // O(n²) - 느림 bool findPair(int arr[], int n, int target) { for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { if(arr[i] + arr[j] == target) return true; } } return false; } ``` **방법 2: 해시맵 사용** ```cpp // O(n) - 빠름! bool findPair(int arr[], int n, int target) { unordered_set seen; for(int i = 0; i < n; i++) { if(seen.count(target - arr[i])) return true; seen.insert(arr[i]); } return false; } ``` ## 9. 실전 가이드라인 ### 입력 크기별 적합한 복잡도 ``` n ≤ 10: O(n!) 가능 n ≤ 20: O(2ⁿ) 가능 n ≤ 500: O(n³) 가능 n ≤ 5,000: O(n²) 가능 n ≤ 100,000: O(n log n) 필요 n ≤ 1,000,000: O(n) 필요 n > 1,000,000: O(log n) 또는 O(1) 필요 ``` ### 어떤 복잡도를 선택할까? 1. **문제 크기 확인**: 입력이 얼마나 클까? 2. **시간 제한 확인**: 보통 1초에 1억 번 연산 가능 3. **적절한 알고리즘 선택**: 위 표 참고 ## 10. 핵심 정리 ### 시간복잡도 - **의미**: 알고리즘 실행 시간 - **중요 이유**: 느린 알고리즘은 현실에서 사용 불가 - **측정 방법**: 입력 크기에 따른 연산 횟수 ### 공간복잡도 - **의미**: 알고리즘이 사용하는 메모리 - **중요 이유**: 메모리도 제한적 자원 - **Trade-off**: 시간 vs 공간 (하나를 희생해 다른 것을 얻음) ### 빅오 표기법 - **최악의 경우** 성능 표현 - **상수 무시**, **가장 큰 항**만 표기 - **O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)** 복잡도 분석은 처음엔 어렵지만, 연습하면 자연스럽게 코드를 보면서 "이건 O(n)이네", "이건 O(n²)이라 느리겠다"라고 판단할 수 있게 됩니다!

[알고리즘] 시간, 공간 복잡도의 개념과 빅오 표기법