시간복잡도(Time Complexity)
알고리즘의 수행시간을 정량화하는 것
계산
일반적으로 1억번의 연산당 1초의 시간이 걸린다고 간주
표기법
일반적으로 빅-오 표기법 사용(Big-O Notation)
- worst case의 연산횟수 나타내는 표기법
- 최고차항의 차수만을 표기
ex. 3n² + 5n + 10 → O(n²) (최고차항인 n²만 남김)
공간복잡도 (Space Complexity)
알고리즘이 사용하는 메모리 크기
c++기준으로,
| 자료형 | 메모리 크기 |
|---|---|
| int | 4byte |
| long long int | 8byte |
| char | 1byte |
ex. int a[5000][5000] ⇒ 4byte 5000 5000 = 100,000,000 = 100MB
