[Algorithm][02] 자료구조 Part: 알고리즘 복잡도 표현 기법

알고리즘 복잡도 계산 항목

=> 어떤 알고리즘이 좋은 알고리즘인지 판단하기 위해 존재 

1. 시간 복잡도 : 알고리즘 실행 속도

2. 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈

 

 

※ 시간 복잡도는 꼭 이해하고 계산할 수 있어야 한다. 공간 복잡도는 중요 X

 

 

※ 알고리즘 시간 복잡도의 주요 요소 : 반복문이 지배한다.

반복문으로 시간 복잡도를 계산한다.

반복문의 구성이 어떠하냐에 따라 시간 복잡도의 차이가 크게 나타난다.

 

 

알고리즘 성능 표기법

Big O (빅-오) 표기법 : O(n)

알고리즘 최악의 실행 시간을 표기

가장 많이/일반적으로 사용함

아무리 최악의 상황이라도, 이 정도의 성능은 보장한다는 의미이기 때문

 

오메가 표기법: 오메가(n)

오메가 표기법은 알고리즘 최상의 실행 시간을 표기

 

세타 표기법: 세타(n)

세타 표기법은 알고리즘 평균 실행 시간을 표기