1. 시간복잡도: 알고리즘을 위해 필요한 연산의 횟수. 즉, 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지를 의미.
2. 공간복잡도: 알고리즘을 위해 필요한 메모리 사이즈. 즉, 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지 의미.
최근 대용량 시스템이 보편화 되면서 공간복잡도 보다 시간복잡도가 중심이 됨.
프로그래밍에서 시간복잡도에 가장 영향을 많이 미치는 요소는 반복문이다.
알고리즘 성능 표기법
1. Big O 표기법
- 알고리즘 최악의 실행 시간 표기
- 아무리 최악의 상황이라도 이정도의 성능은 보장한다는 의미로 일반적으로 많이 사용함
2. 오메가 표기법
- 알고리즘 최상의 실행 시간 표기
3. 세타 표기법
- 알고리즘 평균 실행 시간 표기
시간복잡도의 Big O 표기법
- 너무 설명이 잘 되어 있는 유투브를 발견해서 링크를 걸어둔다.
시간복잡도 계산은 반복문이 핵심 요소임을 기억하자
예시: 1부터 n까지의 합을 구하는 알고리즘
(1) 다음 알고리즘의 Big O notation은 O(n)
def sumALL(n):
total = 0
for num in range(1, n+1): total += num
return total
(2) 다음 알고리즘의 Big O notation은 O(1)
def sumAll(n):
return int(n * (n + 1) / 2)
- 성능이 더 좋은 알고리즘은 O(1)인 두번째 알고리즘이다.
반응형