728x90
시간 복잡도(Time Complexity)
: 인풋 크기에 비례하는 알고리즘의 실행 시간을 나타낸다.
공간 복잡도(Space Complexity)
: 인풋 크기에 비례하여 알고리즘이 사용하는 메모리 공간을 나타낸다.
빅오 표기법(Big-O Notation)
- nnn을 매우 크다고 가정한다.
- 절대적인 시간이 아닌 성장성을 보고 판단한다.
- O(1) : input의 크기가 소요 시간에 영향❌ (반복문이 없는 경우 대체로O(1))
- O(n) : 반복되는 횟수∝ input의 크기
- O(n^2) : 보통 중첩 반복문(반복문 내에 반복문이 있는 경우)
- O(n^3) : 중첩 반복문
- O(lgn) : 보통 두배씩 증가
728x90
'📊 Algorithm > Paradigm' 카테고리의 다른 글
| [Python Plus] Extended Slices [::-1] (0) | 2022.01.25 |
|---|---|
| [알고리즘 대비 - 이코테] 3. 구현 (0) | 2021.09.19 |
| [알고리즘 대비 - 이코테] 2. 그리디 (0) | 2021.08.20 |
| [알고리즘 대비 - 이코테] 1. 자료형 (0) | 2021.06.02 |
| [알고리즘 풀이방법] 알고리즘 패러다임 (0) | 2021.05.26 |