01_complexity.cpp

  1/*
  2 * 시간 복잡도 (Time Complexity)
  3 * Big O Notation and Complexity Analysis
  4 *
  5 * 알고리즘의 효율성을 분석하는 방법입니다.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <algorithm>
 11#include <chrono>
 12#include <functional>
 13
 14using namespace std;
 15
 16// =============================================================================
 17// 1. O(1) - 상수 시간
 18// =============================================================================
 19
 20int constantTime(const vector<int>& arr) {
 21    // 배열 크기와 무관하게 항상 일정한 시간
 22    return arr[0];
 23}
 24
 25// =============================================================================
 26// 2. O(log n) - 로그 시간
 27// =============================================================================
 28
 29int binarySearch(const vector<int>& arr, int target) {
 30    int left = 0, right = arr.size() - 1;
 31
 32    while (left <= right) {
 33        int mid = left + (right - left) / 2;
 34
 35        if (arr[mid] == target)
 36            return mid;
 37        else if (arr[mid] < target)
 38            left = mid + 1;
 39        else
 40            right = mid - 1;
 41    }
 42
 43    return -1;
 44}
 45
 46// =============================================================================
 47// 3. O(n) - 선형 시간
 48// =============================================================================
 49
 50int linearSearch(const vector<int>& arr, int target) {
 51    for (size_t i = 0; i < arr.size(); i++) {
 52        if (arr[i] == target)
 53            return i;
 54    }
 55    return -1;
 56}
 57
 58int sumArray(const vector<int>& arr) {
 59    int sum = 0;
 60    for (int x : arr) {
 61        sum += x;
 62    }
 63    return sum;
 64}
 65
 66// =============================================================================
 67// 4. O(n log n) - 선형 로그 시간
 68// =============================================================================
 69
 70void merge(vector<int>& arr, int left, int mid, int right) {
 71    vector<int> L(arr.begin() + left, arr.begin() + mid + 1);
 72    vector<int> R(arr.begin() + mid + 1, arr.begin() + right + 1);
 73
 74    size_t i = 0, j = 0;
 75    int k = left;
 76
 77    while (i < L.size() && j < R.size()) {
 78        if (L[i] <= R[j])
 79            arr[k++] = L[i++];
 80        else
 81            arr[k++] = R[j++];
 82    }
 83
 84    while (i < L.size()) arr[k++] = L[i++];
 85    while (j < R.size()) arr[k++] = R[j++];
 86}
 87
 88void mergeSort(vector<int>& arr, int left, int right) {
 89    if (left < right) {
 90        int mid = left + (right - left) / 2;
 91        mergeSort(arr, left, mid);
 92        mergeSort(arr, mid + 1, right);
 93        merge(arr, left, mid, right);
 94    }
 95}
 96
 97// =============================================================================
 98// 5. O(n²) - 이차 시간
 99// =============================================================================
100
101void bubbleSort(vector<int>& arr) {
102    int n = arr.size();
103    for (int i = 0; i < n - 1; i++) {
104        for (int j = 0; j < n - i - 1; j++) {
105            if (arr[j] > arr[j + 1]) {
106                swap(arr[j], arr[j + 1]);
107            }
108        }
109    }
110}
111
112int countPairs(const vector<int>& arr) {
113    int count = 0;
114    int n = arr.size();
115    for (int i = 0; i < n; i++) {
116        for (int j = i + 1; j < n; j++) {
117            count++;
118        }
119    }
120    return count;  // n*(n-1)/2
121}
122
123// =============================================================================
124// 6. O(2^n) - 지수 시간
125// =============================================================================
126
127int fibonacciRecursive(int n) {
128    if (n <= 1) return n;
129    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
130}
131
132// O(n) 최적화 버전
133int fibonacciIterative(int n) {
134    if (n <= 1) return n;
135
136    int prev2 = 0, prev1 = 1;
137    for (int i = 2; i <= n; i++) {
138        int curr = prev1 + prev2;
139        prev2 = prev1;
140        prev1 = curr;
141    }
142    return prev1;
143}
144
145// =============================================================================
146// 7. 시간 측정 유틸리티
147// =============================================================================
148
149template<typename Func, typename... Args>
150double measureTime(Func func, Args&&... args) {
151    auto start = chrono::high_resolution_clock::now();
152    func(forward<Args>(args)...);
153    auto end = chrono::high_resolution_clock::now();
154    chrono::duration<double> diff = end - start;
155    return diff.count();
156}
157
158// =============================================================================
159// 8. 공간 복잡도 예제
160// =============================================================================
161
162// O(1) 공간
163void reverseInPlace(vector<int>& arr) {
164    int n = arr.size();
165    for (int i = 0; i < n / 2; i++) {
166        swap(arr[i], arr[n - 1 - i]);
167    }
168}
169
170// O(n) 공간
171vector<int> reverseWithCopy(const vector<int>& arr) {
172    vector<int> result(arr.rbegin(), arr.rend());
173    return result;
174}
175
176// =============================================================================
177// 테스트
178// =============================================================================
179
180void printArray(const vector<int>& arr, int limit = 10) {
181    cout << "    [";
182    for (size_t i = 0; i < arr.size() && i < (size_t)limit; i++) {
183        cout << arr[i];
184        if (i < arr.size() - 1 && i < (size_t)limit - 1) cout << ", ";
185    }
186    if (arr.size() > (size_t)limit) cout << ", ...";
187    cout << "]" << endl;
188}
189
190int main() {
191    cout << "============================================================" << endl;
192    cout << "시간 복잡도 (Time Complexity) 예제" << endl;
193    cout << "============================================================" << endl;
194
195    // 1. O(1)
196    cout << "\n[1] O(1) - 상수 시간" << endl;
197    vector<int> arr1 = {5, 2, 8, 1, 9};
198    cout << "    첫 번째 원소: " << constantTime(arr1) << endl;
199
200    // 2. O(log n)
201    cout << "\n[2] O(log n) - 이분 탐색" << endl;
202    vector<int> arr2 = {1, 3, 5, 7, 9, 11, 13, 15};
203    int idx = binarySearch(arr2, 7);
204    cout << "    배열: [1,3,5,7,9,11,13,15]" << endl;
205    cout << "    7의 위치: " << idx << endl;
206
207    // 3. O(n)
208    cout << "\n[3] O(n) - 선형 탐색" << endl;
209    vector<int> arr3 = {4, 2, 7, 1, 9, 3};
210    cout << "    배열 합: " << sumArray(arr3) << endl;
211
212    // 4. O(n log n)
213    cout << "\n[4] O(n log n) - 병합 정렬" << endl;
214    vector<int> arr4 = {64, 34, 25, 12, 22, 11, 90};
215    cout << "    정렬 전: ";
216    printArray(arr4);
217    mergeSort(arr4, 0, arr4.size() - 1);
218    cout << "    정렬 후: ";
219    printArray(arr4);
220
221    // 5. O(n²)
222    cout << "\n[5] O(n²) - 버블 정렬" << endl;
223    vector<int> arr5 = {64, 34, 25, 12, 22, 11, 90};
224    bubbleSort(arr5);
225    cout << "    정렬 후: ";
226    printArray(arr5);
227    cout << "    5개 원소의 쌍 개수: " << countPairs(vector<int>(5)) << endl;
228
229    // 6. O(2^n) vs O(n)
230    cout << "\n[6] O(2^n) vs O(n) - 피보나치" << endl;
231    cout << "    피보나치(20) 재귀: " << fibonacciRecursive(20) << endl;
232    cout << "    피보나치(20) 반복: " << fibonacciIterative(20) << endl;
233    cout << "    피보나치(40) 반복: " << fibonacciIterative(40) << endl;
234
235    // 7. 공간 복잡도
236    cout << "\n[7] 공간 복잡도" << endl;
237    vector<int> arr7 = {1, 2, 3, 4, 5};
238    cout << "    원본: ";
239    printArray(arr7);
240    reverseInPlace(arr7);
241    cout << "    O(1) 공간 뒤집기: ";
242    printArray(arr7);
243
244    // 8. 복잡도 요약
245    cout << "\n[8] 복잡도 요약" << endl;
246    cout << "    | 복잡도    | 1000개 연산 | 예시              |" << endl;
247    cout << "    |-----------|-------------|-------------------|" << endl;
248    cout << "    | O(1)      | 1           | 배열 인덱싱       |" << endl;
249    cout << "    | O(log n)  | 10          | 이분 탐색         |" << endl;
250    cout << "    | O(n)      | 1000        | 선형 탐색         |" << endl;
251    cout << "    | O(n log n)| 10000       | 병합 정렬         |" << endl;
252    cout << "    | O(n²)     | 1000000     | 버블 정렬         |" << endl;
253    cout << "    | O(2^n)    | 매우 큼     | 모든 부분집합     |" << endl;
254
255    cout << "\n============================================================" << endl;
256
257    return 0;
258}