시간 복잡도 & 공간 복잡도
<aside>
- 알고리즘을 평가하는 경우 시간 복잡도 & 공간 복잡도를 사용
- 시간 복잡도 : 알고리즘의 수행시간을 평가
- 공간 복잡도 : 알고리즘의 수행에 필요한 메모리 양을 평가
</aside>
시간 복잡도
<aside>
- 알고리즘의 수행 시간을 분석할 때 시간 복잡도를 사용
- 수행 시간은 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가
기본 연산
- 데이터 입출력 : copy, move …
- 산술 연산 : add, multiply …
- 제어 연산 : if, while …
시간 복잡도
- 최선의 경우(Best Case)
- 빅 오메가 표기법 사용
- 최선의 시나리오로 최소 이만한 시간이 걸림
- 최악의 경우(Wost Case)
- 빅 오 표기법 사용
- 최악의 시나리오로 아무리 오래 걸려도 이 시간보다 덜 걸림
- 평균의 경우(Average Case)
- 빅 세타 표기법 사용
- 평균 시간을 나타냄
</aside>
시간 복잡도 계산
<aside>
- 시간 복잡도는 일반적으로 빅오 표기법을 사용
- 연산 횟수가 다항식으로 표현될 경우, 최고차항을 제외한 모든 항의 최고차항의 계수를 제외시켜 나타냄
예시
</aside>
빅오 표기법 종류(Big-O)
<aside>
- O(1)
- O(n)
- O(log n)
- O(n^2)
- O(2^n)
</aside>
O(1) - 상수 시간(Constant time)