01_complexity.c

Download
c 270 lines 7.8 KB 
  1/*
  2 * ์‹œ๊ฐ„ ๋ณต์žก๋„ (Time Complexity)
  3 * Big O Notation and Complexity Analysis
  4 *
  5 * ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํšจ์œจ์„ฑ์„ ๋ถ„์„ํ•˜๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <time.h>
 11
 12/* =============================================================================
 13 * 1. O(1) - ์ƒ์ˆ˜ ์‹œ๊ฐ„
 14 * ============================================================================= */
 15
 16int constant_time(int arr[], int n) {
 17    /* ๋ฐฐ์—ด ํฌ๊ธฐ์™€ ๋ฌด๊ด€ํ•˜๊ฒŒ ํ•ญ์ƒ ์ผ์ •ํ•œ ์‹œ๊ฐ„ */
 18    return arr[0];
 19}
 20
 21/* =============================================================================
 22 * 2. O(log n) - ๋กœ๊ทธ ์‹œ๊ฐ„
 23 * ============================================================================= */
 24
 25int binary_search(int arr[], int n, int target) {
 26    int left = 0, right = n - 1;
 27
 28    while (left <= right) {
 29        int mid = left + (right - left) / 2;
 30
 31        if (arr[mid] == target)
 32            return mid;
 33        else if (arr[mid] < target)
 34            left = mid + 1;
 35        else
 36            right = mid - 1;
 37    }
 38
 39    return -1;
 40}
 41
 42/* =============================================================================
 43 * 3. O(n) - ์„ ํ˜• ์‹œ๊ฐ„
 44 * ============================================================================= */
 45
 46int linear_search(int arr[], int n, int target) {
 47    for (int i = 0; i < n; i++) {
 48        if (arr[i] == target)
 49            return i;
 50    }
 51    return -1;
 52}
 53
 54int sum_array(int arr[], int n) {
 55    int sum = 0;
 56    for (int i = 0; i < n; i++) {
 57        sum += arr[i];
 58    }
 59    return sum;
 60}
 61
 62/* =============================================================================
 63 * 4. O(n log n) - ์„ ํ˜• ๋กœ๊ทธ ์‹œ๊ฐ„
 64 * ============================================================================= */
 65
 66void merge(int arr[], int left, int mid, int right) {
 67    int n1 = mid - left + 1;
 68    int n2 = right - mid;
 69
 70    int *L = malloc(n1 * sizeof(int));
 71    int *R = malloc(n2 * sizeof(int));
 72
 73    for (int i = 0; i < n1; i++)
 74        L[i] = arr[left + i];
 75    for (int j = 0; j < n2; j++)
 76        R[j] = arr[mid + 1 + j];
 77
 78    int i = 0, j = 0, k = left;
 79    while (i < n1 && j < n2) {
 80        if (L[i] <= R[j])
 81            arr[k++] = L[i++];
 82        else
 83            arr[k++] = R[j++];
 84    }
 85
 86    while (i < n1)
 87        arr[k++] = L[i++];
 88    while (j < n2)
 89        arr[k++] = R[j++];
 90
 91    free(L);
 92    free(R);
 93}
 94
 95void merge_sort(int arr[], int left, int right) {
 96    if (left < right) {
 97        int mid = left + (right - left) / 2;
 98        merge_sort(arr, left, mid);
 99        merge_sort(arr, mid + 1, right);
100        merge(arr, left, mid, right);
101    }
102}
103
104/* =============================================================================
105 * 5. O(nยฒ) - ์ด์ฐจ ์‹œ๊ฐ„
106 * ============================================================================= */
107
108void bubble_sort(int arr[], int n) {
109    for (int i = 0; i < n - 1; i++) {
110        for (int j = 0; j < n - i - 1; j++) {
111            if (arr[j] > arr[j + 1]) {
112                int temp = arr[j];
113                arr[j] = arr[j + 1];
114                arr[j + 1] = temp;
115            }
116        }
117    }
118}
119
120int count_pairs(int arr[], int n) {
121    int count = 0;
122    for (int i = 0; i < n; i++) {
123        for (int j = i + 1; j < n; j++) {
124            count++;
125        }
126    }
127    return count;  /* n*(n-1)/2 */
128}
129
130/* =============================================================================
131 * 6. O(2^n) - ์ง€์ˆ˜ ์‹œ๊ฐ„
132 * ============================================================================= */
133
134int fibonacci_recursive(int n) {
135    if (n <= 1)
136        return n;
137    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
138}
139
140/* O(n) ์ตœ์ ํ™” ๋ฒ„์ „ */
141int fibonacci_iterative(int n) {
142    if (n <= 1)
143        return n;
144
145    int prev2 = 0, prev1 = 1;
146    for (int i = 2; i <= n; i++) {
147        int curr = prev1 + prev2;
148        prev2 = prev1;
149        prev1 = curr;
150    }
151    return prev1;
152}
153
154/* =============================================================================
155 * 7. ์‹œ๊ฐ„ ์ธก์ • ์œ ํ‹ธ๋ฆฌํ‹ฐ
156 * ============================================================================= */
157
158double measure_time(void (*func)(int*, int), int arr[], int n) {
159    clock_t start = clock();
160    func(arr, n);
161    clock_t end = clock();
162    return (double)(end - start) / CLOCKS_PER_SEC;
163}
164
165/* =============================================================================
166 * 8. ๊ณต๊ฐ„ ๋ณต์žก๋„ ์˜ˆ์ œ
167 * ============================================================================= */
168
169/* O(1) ๊ณต๊ฐ„ */
170void reverse_in_place(int arr[], int n) {
171    for (int i = 0; i < n / 2; i++) {
172        int temp = arr[i];
173        arr[i] = arr[n - 1 - i];
174        arr[n - 1 - i] = temp;
175    }
176}
177
178/* O(n) ๊ณต๊ฐ„ */
179int* reverse_with_copy(int arr[], int n) {
180    int *result = malloc(n * sizeof(int));
181    for (int i = 0; i < n; i++) {
182        result[i] = arr[n - 1 - i];
183    }
184    return result;
185}
186
187/* =============================================================================
188 * ํ…Œ์ŠคํŠธ
189 * ============================================================================= */
190
191void print_array(int arr[], int n) {
192    printf("    [");
193    for (int i = 0; i < n && i < 10; i++) {
194        printf("%d", arr[i]);
195        if (i < n - 1 && i < 9) printf(", ");
196    }
197    if (n > 10) printf(", ...");
198    printf("]\n");
199}
200
201int main(void) {
202    printf("============================================================\n");
203    printf("์‹œ๊ฐ„ ๋ณต์žก๋„ (Time Complexity) ์˜ˆ์ œ\n");
204    printf("============================================================\n");
205
206    /* 1. O(1) */
207    printf("\n[1] O(1) - ์ƒ์ˆ˜ ์‹œ๊ฐ„\n");
208    int arr1[] = {5, 2, 8, 1, 9};
209    printf("    ์ฒซ ๋ฒˆ์งธ ์›์†Œ: %d\n", constant_time(arr1, 5));
210
211    /* 2. O(log n) */
212    printf("\n[2] O(log n) - ์ด๋ถ„ ํƒ์ƒ‰\n");
213    int arr2[] = {1, 3, 5, 7, 9, 11, 13, 15};
214    int idx = binary_search(arr2, 8, 7);
215    printf("    ๋ฐฐ์—ด: [1,3,5,7,9,11,13,15]\n");
216    printf("    7์˜ ์œ„์น˜: %d\n", idx);
217
218    /* 3. O(n) */
219    printf("\n[3] O(n) - ์„ ํ˜• ํƒ์ƒ‰\n");
220    int arr3[] = {4, 2, 7, 1, 9, 3};
221    printf("    ๋ฐฐ์—ด ํ•ฉ: %d\n", sum_array(arr3, 6));
222
223    /* 4. O(n log n) */
224    printf("\n[4] O(n log n) - ๋ณ‘ํ•ฉ ์ •๋ ฌ\n");
225    int arr4[] = {64, 34, 25, 12, 22, 11, 90};
226    printf("    ์ •๋ ฌ ์ „: ");
227    print_array(arr4, 7);
228    merge_sort(arr4, 0, 6);
229    printf("    ์ •๋ ฌ ํ›„: ");
230    print_array(arr4, 7);
231
232    /* 5. O(nยฒ) */
233    printf("\n[5] O(nยฒ) - ๋ฒ„๋ธ” ์ •๋ ฌ\n");
234    int arr5[] = {64, 34, 25, 12, 22, 11, 90};
235    bubble_sort(arr5, 7);
236    printf("    ์ •๋ ฌ ํ›„: ");
237    print_array(arr5, 7);
238    printf("    5๊ฐœ ์›์†Œ์˜ ์Œ ๊ฐœ์ˆ˜: %d\n", count_pairs(arr5, 5));
239
240    /* 6. O(2^n) vs O(n) */
241    printf("\n[6] O(2^n) vs O(n) - ํ”ผ๋ณด๋‚˜์น˜\n");
242    printf("    ํ”ผ๋ณด๋‚˜์น˜(20) ์žฌ๊ท€: %d\n", fibonacci_recursive(20));
243    printf("    ํ”ผ๋ณด๋‚˜์น˜(20) ๋ฐ˜๋ณต: %d\n", fibonacci_iterative(20));
244    printf("    ํ”ผ๋ณด๋‚˜์น˜(40) ๋ฐ˜๋ณต: %d\n", fibonacci_iterative(40));
245
246    /* 7. ๊ณต๊ฐ„ ๋ณต์žก๋„ */
247    printf("\n[7] ๊ณต๊ฐ„ ๋ณต์žก๋„\n");
248    int arr7[] = {1, 2, 3, 4, 5};
249    printf("    ์›๋ณธ: ");
250    print_array(arr7, 5);
251    reverse_in_place(arr7, 5);
252    printf("    O(1) ๊ณต๊ฐ„ ๋’ค์ง‘๊ธฐ: ");
253    print_array(arr7, 5);
254
255    /* 8. ๋ณต์žก๋„ ์š”์•ฝ */
256    printf("\n[8] ๋ณต์žก๋„ ์š”์•ฝ\n");
257    printf("    | ๋ณต์žก๋„    | 1000๊ฐœ ์—ฐ์‚ฐ | ์˜ˆ์‹œ              |\n");
258    printf("    |-----------|-------------|-------------------|\n");
259    printf("    | O(1)      | 1           | ๋ฐฐ์—ด ์ธ๋ฑ์‹ฑ       |\n");
260    printf("    | O(log n)  | 10          | ์ด๋ถ„ ํƒ์ƒ‰         |\n");
261    printf("    | O(n)      | 1000        | ์„ ํ˜• ํƒ์ƒ‰         |\n");
262    printf("    | O(n log n)| 10000       | ๋ณ‘ํ•ฉ ์ •๋ ฌ         |\n");
263    printf("    | O(nยฒ)     | 1000000     | ๋ฒ„๋ธ” ์ •๋ ฌ         |\n");
264    printf("    | O(2^n)    | ๋งค์šฐ ํผ     | ๋ชจ๋“  ๋ถ€๋ถ„์ง‘ํ•ฉ     |\n");
265
266    printf("\n============================================================\n");
267
268    return 0;
269}