> For the complete documentation index, see [llms.txt](https://nelmm.gitbook.io/til/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nelmm.gitbook.io/til/algorithm/computational-complexity.md).
# 복잡도 계산 ( 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 ) 에서도 최소 이 정도 성능은 보장된다. 이고 **오메가**는 알고리즘의 최고 성능을, **세타**는 평균 성능을 표시 해주기 때문에 최악의 경우를 보여주는 빅오 알고리즘을 주로 사용한다.