복잡도 계산 ( Computational Complexity )
Last updated
Last updated
계산 문제를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법.
기준은 소요 시간과 메모리 사용량 등 자원이다. (이는 입력의 크기에 비례한다. )
프로그램의 규모가 점점 커짐에 따라 입력하는 데이터가 많아질수록 알고리즘간의 효율의 차이가 커지기 때문에 알고리즘의 복잡도를 계산하여 효율적인 알고리즘을 선택해야한다.
입력의 크기가 충분히 클 때의 시간복잡도와 공간복잡도를 분석하는 것.
프로그램의 입력 크기 등 성능을 결정하는 주요 특성 값이 매우 클 때의 프로그램의 성능.
프로그램의 실행 속도가 어떤 경향을 가지는지를 평가한다고 생각하면 된다.
ex. 입력의 크기가 n이고 n이 매우 큰 경우
프로그램 성능 평가의 매우 중요한 기준.
어떠한 문제 해결을 위한 알고리즘의 성능분석을 할 때, 주어지는 데이터의 형태나 실험을 수행하는 환경, 또는 실험에 사용한 시스템의 성능등 다양한 요소에 의해 공평한 결과가 나오기 힘들고 비교 결과가 항상 일정하지 않을 수 있다.
이를 효과적으로 해결하는 방법이 점근적 분석법이다. 점근적 분석법은 각 알고리즘이 주어진 데이터의 크기를 기준으로 수행시간 혹은 사용공간이 얼마나 되는지를 객관적으로 비교할 수 있는 기준을 제시해 준다.
O(빅오), Ω(오메가), Θ(세타)등이 있다. 일반적으로 빅오와 세타표기가 많이 사용된다.
가장 왼쪽부터 빅오, 오메가, 세타 그래프이다.
점근적 상한선(Asymptotic upper bound)
주어진 알고리즘이 아무리 나빠도 비교하는 함수와 같거나 좋다.
정의 : O(g(n)) = {f(n) : there exist positive constants c and n0 such that 0≤f(n)≤cg(n) for all n≥n0}
n0를 기준으로 n0보다 오른쪽에 있는 모든 n 값에 대해 함수 f(n)은 함수 cg(n)보다 작거나 같다는 의미이다. 그래프가 아래에 있을 수록 수행시간이 짧은 것이므로 성능이 좋은 것이다.
어떤 알고리즘의 가장 최악인경우 ( Wort Case )를 보여주기 때문에 많이 사용된다.
점근적 하한선(Asymptotic lower bound)
주어진 알고리즘이 아무리 좋아도 비교하는 함수와 같거나 나쁘다.
정의 : Ω(g(n)) = {f(n) : there exist positive constants c and n0 such that 0≤cg(n)≤f(n) for all n≥n0}
n0를 기준으로 n0보다 오른쪽에 있는 모든 n 값에 대해 함수 f(n)은 함수 cg(n)보다 크거나 같다는 의미이다.
어떤 알고리즘의 가장 최선의경우 ( best case )를 보여준다.
점근선 상한선과 점근적 하한선의 교집합(Asymptotic tighter bound)
주어진 알고리즘이 아무리 좋아지거나 나빠지더라도 비교하는 함수의 범위안에 있다.
정의 : Θ(g(n)) = {f(n) : there exist positive constants c1, c2 and n0 such that 0≤c1g(n)≤f(n)≤c2g(n) for all n≥n0}
n0를 기준으로 n0보다 오른쪽에 있는 모든 n 값에 대해 함수 f(n)은 함수 c1g(n)보다 크거나 같거나 c2g(n)보다 작거나 같다는 의미이다
어떤 알고리즘의 평균 ( average case ) 을 보여준다.
알고리즘의 시간을 측정했을 때 예를 들어 이 알고리즘은 평균 15초 정도 걸려요 보다 이 알고리즘은 최대 20초는 넘게 안걸립니다 가 최소 성능을 보장하며 신뢰가 있기 때문이다.
어떤 알고리즘의 시간, 공간 복잡도를 측정 할 경우 best case, average case, best case의 경우가 나오는 데 빅오 표기법이 가장 최악의 상황 ( best case ) 에서도 최소 이 정도 성능은 보장된다. 이고 오메가는 알고리즘의 최고 성능을, 세타는 평균 성능을 표시 해주기 때문에 최악의 경우를 보여주는 빅오 알고리즘을 주로 사용한다.