시간 복잡도 : 알고리즘 복잡도 표현 방법

하나의 문제를 푸는 알고리즘은 다양하다. 

다양한 알고리즘 중에 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산하는 것이다.

 

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

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

 

알고리즘 시간 복잡도의 주요요소는 반복문이다.

 

3. 알고리즘 성능 표기법

• Big O(빅-오)표기법 : O(N)

알고리즘 최악의 실행 시간을 표시한다.

가장 일반적으로 사용한다.

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

 

• Ω (오메가) 표기법: Ω(N)

알고리즘 최상의 실행시간을 표기한다.

 

• Θ (세타) 표기법: Θ(N)

알고리즘 평균 실행시간을 표기한다.

 

4. O(N) 빅오 표기법입력 n에 따라 결정되는 시간 복잡도 함수이다.O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!)