시간 복잡도란(Time complexity)?
특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간
시간 복잡도는 주로 빅오 표기법을 사용
최선, 평균, 최악으로 나누어서 표기함
최선 : 실행 시간이 가장 빠른 경우
평균 : 평균 수행 시간
최악 : 실행 시간이 가장 느릴 경우
ex) 퀵정렬의 경우 최선, 평균 시간복잡도는 O(nlogn)이며, 최악 시간복잡도는 O(n²)
빅오 표기법
알고리즘의 효율을 분석하고 비교하는데 쓰이는 개념
최악의 경우를 고려하여 쓰여짐
상한 점근 표기법
계수와 낮은 항을 제외시킴
ex) 3n² + 2n -1 => O(n²)
ex) 3n => O(n)
ex) 10 => O(1)
공간 복잡도란(Space complexity)?
프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양
총 공간 요구 = 고정 공간 요구 + 가변 공간 요구
S(P)=c+SP(n)
고정 공간
코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수
가변 공간
동적으로 필요한 공간
* 시간 복잡도와 공간 복잡도는 반비례적 경향이 있음
* 알고리즘의 척도는 시간 복잡도 위주로 판단
'자료구조' 카테고리의 다른 글
| 구조체, typedef (0) | 2021.05.03 |
|---|---|
| 포인터, 이중 포인터, Call by value, Call by reference (0) | 2021.05.03 |
| [자료구조] 정렬 알고리즘 (0) | 2021.03.02 |
| [자료구조] Comparison Sort, In-place Sort (비교 정렬, 제자리 정렬) (0) | 2021.03.02 |
| [자료구조] Stable Sort, Unstable Sort (안정 정렬, 불안정 정렬) (0) | 2021.03.02 |