[자료구조] 기초 - 자료 복잡도

알고리즘 복잡도(complexity)

 알고리즘의 복잡도는 n개의 자료가 사용하여 알고리즘을 작성하였을 경우 알고리즘을 수행하는데 걸리는 시간을 n에 비례하여 표현한다.
기본적으로 n개의 자료를 가지고있는 자료 알고리즘의 실행시간이 n개의 자료에 비례한다는 의미에서 O(n)을 사용한다.


알고리즘 효율 관계 (n)

상수 > log2n > n > nlog2n > n² > n³ > 2ⁿ


O(c) 상수 효율

c는 상수이다. 즉, n의 자리에 변수가아니라 상수가 들어가는 경우이다.
이 경우 복잡도는 항상 x축에 수평이므로, 알고리즘의 수행에 걸리는 시간이 자료 집합의 크기에 상관없으며, 그 수행 시간은 항상 일정하다.


O(log₂n) 로그 효율

밑수가 2인 로그함수의 복잡도는 자료집합의 크기가 두배가 될때마다 수행시간은 1씩 증가한다.
로그기반 알고리즘은 자료의 크기와 독립적인 O(c)를 제외하고, 자료의 크기에 의존적인 알고리즘들 중에서 가장 효율적이다.


O(n) 선형 효율

자료집합의 크기가 증가함에 따라 일정한 비율로 완만하게 증가한다.


O(nlog₂n) 선형 지수 효율

 정렬 알고리즘이 목표로하는 최소한의 복잡도이다.
잘 짜여진 트리라던가, 이분 검색, 퀵 정렬과 같은 알고리즘에서 볼 수 있다.

O(n²) 제곱 효율

자료집합이 증가함에 따라 그 수행시간이 급격히 증가하는 경우이다.
대표적으로 for문 안에 for문이 내포된 경우


O(n³) 세제곱 효율

 제곱 효율보다 수행시간이 오래걸리므로 성능이 좋지 못한 복잡도이다.

대표적인 알고리즘으로는 Floyd 알고리즘이 있으며 Floyd 알고리즘과 같이 for문이 3겹으로 사용되거나 하는 경우이다.

덧붙여서 Floyd 알고리즘은 좋지못한 효율을 보임에도 불구하고 간단한 코딩방식 덕분에 많은 사람들에게 애용되고 있다 (...)


O(2ⁿ) 지수 효율

자료의 개수가 1개 증가할 때마다 수행시간이 2의 지수배로 증가하는 매우 비효율적인 경우의 복잡도이다.