데이터 구조 - (2) 알고리즘의 성능

입력의 크기

출처 : 쉽게 배우는 자료구조 with 파이썬

각 알고리즘 마다 수행 시간이 다르다.

입력의 크기가 작으면 알고리즘 마다의 시간 차이도

적어서 괜찮은 경우가 많지만, n의 크기가 커질수록

그 시간 차이도 상당히 커지기에 알고리즘의 성능이 중요해진다.

​

출처 : 쉽게 배우는 자료구조 with 파이썬

위와 같이 1번째는 n이 엄청 커져도 결국 나누기 2를 하기에 상수 시간이 걸린다.

2번째 경우는 n이 커질수록 for문의 반복횟수가 늘기에 n에 비례한다.

3번째 경우는 n이 커질수록 이중 for문과 수행시간을 확인해보면 n(n-1)/2로 n제곱에 비례한다.

 

알고리즘 복잡도

점근적 복잡도 : 입력의 크기가 충분히 클 때의 복잡도

출처 : 쉽게 배우는 자료구조 with 파이썬

차례대로 위의 기호는 "빅오", "빅 오메가", "빅 세타"라고 부른다.

빅오는 최대를 정의하고, 빅 오메가는 최소를 정의하고, 빅 세타는 둘의 교집합을 정의한다.

그렇기에 오메가는 최대가 어느정도가 되는지 모르기에 알고리즘의 성능을

예측하기 어렵고 잘 사용하지 않는다.

​

출처 : 쉽게 배우는 자료구조 with 파이썬

점근적 복잡도의 수학적 정의는 위와 같다.

또한 점근적 표기에서의 "="은 "∈"와 같은 의미를 가진다.

T(n) = O(nlogn)이라 하면 T(n) ∈ O(nlogn)이란 뜻이다. 속하는 함수정도로 해석할 수 있다.

출처 : 쉽게 배우는 자료구조 with 파이썬

 

알고리즘 표기법 사용해 보기

출처 : 쉽게 배우는 자료구조 with 파이썬

출처 : 쉽게 배우는 자료구조 with 파이썬

빅 오와 빅 오메가 둘 다 표현이 가능하다면 빅 세타로 표현해준다.

표현하는 것이 둘 다 가능하다고 해도 최대한 정보의 손실이

적은 쪽으로 알고리즘 표기를 해주어야 한다.

​

+ 마스터 정리

출처 : 쉽게 배우는 자료구조 with 파이썬

출처 : 쉽게 배우는 자료구조 with 파이썬