알고리즘 스터디를 제대로 시작하기 전에, 알아야 할 것 같은 몇가지 개념들을 정리 해 보려고 한다.
1. 복잡도 : 알고리즘의 성능을 나타내는 척도. 시간 복잡도와 공간 복잡도 두 종류로 나누어지며 복잡도가 낮을수록 좋은 알고리즘임.
대체로 '복잡도'라고만 언급된다면 시간복잡도를 뜻함.
가. 시간복잡도 : 알고리즘 수행을 위해 필요한 시간(연산의 횟수)
| 빅오 표기법 | 명 칭 | N이 1,000일 때, 연산 횟수 |
| O(1) | 상수 시간 | 1 |
| O(logN) | 로그 시간 | 3 |
| O(N) | 선형 시간 | 1,000 |
| O(NlogN) | 로그 선형 시간 | 10,000 |
| O(N²) | 이차 시간 | 1,000,000 |
| O(N³) | 삼차 시간 | 1,000,000,000 |
| O(2^n) | 지수 시간 | 약 10^301 |
import time
start_time = time.time() # 측정 시작시간
# 기타 프로그램 코드
end_time = time.time() # 측정 종료시간
print('time: ', end_time - start_time) # 소요시간 출력< 대략적인 시간복잡도 측정방법 >
나. 공간복잡도 : 알고리즘 수행을 위해 필요한 메모리의 양.
일반적으로 128~512MB정도로, 데이터의 개수가 1,000만 단위가 넘지 않도록 설계 할 것.
