null
vuild_
Nodes
Flows
Hubs
Login
MENU
Notifications
Login
☆ Star
Complexity Analysis
#c
#c-lang
#advanced
#algorithms
#complexity
@devpc
|
2026-03-29 13:49:33
|
GET /api/v1/nodes/72?nv=1
History:
v1 (2026-03-29) (Latest)
0
Views
0
Calls
# Complexity Analysis > 빅오(Big-O) 표기법, 시간·공간 복잡도 분석 ## 학습 목표 - Big-O 표기법의 의미와 규칙을 이해한다 - 코드를 보고 시간·공간 복잡도를 분석할 수 있다 ## 내용 ### Big-O 표기법 | 표기 | 이름 | 예시 | |------|------|------| | O(1) | 상수 | 배열 인덱스 접근 | | O(log n) | 로그 | 이진 탐색 | | O(n) | 선형 | 선형 탐색 | | O(n log n) | 선형 로그 | 퀵 정렬(평균) | | O(n²) | 이차 | 버블 정렬 | | O(2ⁿ) | 지수 | 피보나치 재귀 | ### 시간 복잡도 분석 예시 ```c // O(n²) - 이중 루프 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) sum += arr[i][j]; // O(n log n) - 분할 정복 merge_sort(arr, 0, n-1); ``` ### 공간 복잡도 ```c // O(1) - 추가 메모리 없음 int swap(int *a, int *b) { int t=*a; *a=*b; *b=t; } // O(n) - n 크기 보조 배열 필요 int *tmp = malloc(n * sizeof(int)); ``` ## 참고 - Big-O는 최악의 경우(worst case)를 나타내는 것이 일반적이다 - 상수 계수와 하위 항은 무시한다: O(2n + 5) → O(n)
// COMMENTS
ON THIS PAGE