복잡도 계산 ( Computational Complexity )
계산 문제를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법.
기준은 소요 시간과 메모리 사용량 등 자원이다. (이는 입력의 크기에 비례한다. )
프로그램의 규모가 점점 커짐에 따라 입력하는 데이터가 많아질수록 알고리즘간의 효율의 차이가 커지기 때문에 알고리즘의 복잡도를 계산하여 효율적인 알고리즘을 선택해야한다.
◼ 점근 계산 복잡도 ( Asymptotic Complexity)
입력의 크기가 충분히 클 때의 시간복잡도와 공간복잡도를 분석하는 것.
프로그램의 입력 크기 등 성능을 결정하는 주요 특성 값이 매우 클 때의 프로그램의 성능.
프로그램의 실행 속도가 어떤 경향을 가지는지를 평가한다고 생각하면 된다.
ex. 입력의 크기가 n이고 n이 매우 큰 경우
프로그램 성능 평가의 매우 중요한 기준.
✔ 점근적 분석의 필요성
어떠한 문제 해결을 위한 알고리즘의 성능분석을 할 때, 주어지는 데이터의 형태나 실험을 수행하는 환경, 또는 실험에 사용한 시스템의 성능등 다양한 요소에 의해 공평한 결과가 나오기 힘들고 비교 결과가 항상 일정하지 않을 수 있다.
이를 효과적으로 해결하는 방법이 점근적 분석법이다. 점근적 분석법은 각 알고리즘이 주어진 데이터의 크기를 기준으로 수행시간 혹은 사용공간이 얼마나 되는지를 객관적으로 비교할 수 있는 기준을 제시해 준다.
O(빅오), Ω(오메가), Θ(세타)등이 있다. 일반적으로 빅오와 세타표기가 많이 사용된다.
✔ 빅오 표기법 ( O Notation )
점근적 상한선(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 )를 보여주기 때문에 많이 사용된다.
✔ 오메가 표기법 ( Ω Notation )
점근적 하한선(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 )를 보여준다.
✔ 세타 표기법 ( Θ Notation )
점근선 상한선과 점근적 하한선의 교집합(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 ) 에서도 최소 이 정도 성능은 보장된다. 이고 오메가는 알고리즘의 최고 성능을, 세타는 평균 성능을 표시 해주기 때문에 최악의 경우를 보여주는 빅오 알고리즘을 주로 사용한다.
Last updated
