점근적 분석과 표기법 : 시간 복잡도와 공간 복잡도

시간 복잡도

알고리즘의 연산 수에 따른 수행시간

공간 복잡도

알고리즘이 소요 하는 메모리의 사용량

---

점근적 분석을 해야 하는 이유

문제를 알고리즘으로 푸는 방법은 하나만 있지 않고 다양한 방법이 있습니다.

다양한 방법과 하드웨어 및 상황에 따라 성능이 좌지우지 됩니다.

문제를 해결하는 알고리즘이 최적의 성능을 낼 수 있는지 확인 할 필요가 있습니다.

점근적 분석이란

입력 되는 데이터의 크기에 따라 수행 시간과 공간을 얼마나 차지하는지를 측정합니다.

이를 통해 효율적인 알고리즘인지를 판단합니다.

정확한것은 아니고 대략 이런식으로 수행시간이 나온다라는걸 측정하는 용도로 사용합니다.

측정의 용도로 사용하기에 최악의 경우를 측정 할 수 있는 빅오 표기법을 주로 사용합니다.

복잡도를 표현하는 방법으로 O(빅오), Ω(오메가), Θ(세타)가 있습니다.

---

O(빅오 표기법)

 - 점근적 상한선 : '최악의 경우'를 전제로 최대치에서 알고리즘과 비교합니다.

"아무리 알고리즘이 나빠도 비교 함수와 같거나 좋다."

수학적 표현 :  C( n² + 2n + 1 ) = O(n²) 

연산 시간 비교 : O( 1) < O( log n) < O( n) < O( n* log n ) < O( n²) < O( n³)  < O( 2n ) < O( n! ) 

표기법 유형 

- O(1)

- O(n)

- O(n+m)

- O(nm)

- O(3n)

- O(n^2)

- O(nlogn)

- O(n!)

표기법 설명

- O( 1)  : 입력 데이터와 상관 없이 일정한 실행 시간을 갖는 알고리즘을 뜻합니다.

- O( log n)  : 입력 데이터가 증가하면 실행 시간이 조금씩 증가하는 알고리즘을 뜻합니다.

-> 성능 좋은 탐색 알고리즘은 대부분 log n의 수행 시간을 갖습니다.

- O( n)  : 입력 데이터 수와 비례하여 선형적으로 증가하는 알고리즘을 뜻합니다.

- O( n* log n )  : 입력 데이터가 늘어난 양보다 조금 더 늘어난 수행 시간을 갖는 알고리즘을 뜻합니다.

-> 커다란 문제를 나누어 해결하고 이를 다시 합치는 과정에서 나타냅니다.

- O( n² )  : 입력 데이터가 커질수록 배수로 늘어나는 수행시간을 갖는 알고리즘을 뜻합니다.

-> n이 두배면 수행 시간은 네배로 늘어나고 데이터가 많으면 감당 할 수 없습니다.

- O( n³ )  : 입력 데이터가 커질수록 배수로 늘어나는 수행시간을 갖는 알고리즘을 뜻합니다.

-> n이 두배면 수행 시간은 여덟배로 늘어나고 데이터가 많으면 감당 할 수 없습니다.

- O( 2n )  : 입력 데이터가 증가하면 수행 시간이 급격하게 증가하는 알고리즘을 뜻합니다.

-> 다른 방법을 찾아야 하며 이는 흔하지 않은 알고리즘입니다.

- O( n! )  : 입력 데이터에 따라 입력 데이터 양의 팩토리얼만큼 증가

-> 2, 4, 8, 16 ...

Ω(오메가 표기법)

- 점근적 하한선 : '최선의 경우'를 전제로 최소치에서 알고리즘을 비교합니다.

"아무리 알고리즘이 좋아도 비교 함수와 같거나 나쁘다."

빅 오메가와 반대입니다.

Θ(세타 표기법)

- 점근적 상한선과 하한선의 교집합 : "최악과 최선의 중간 어느지점"을 범위를 전제로 알고리즘 비교합니다.

"아무리 알고리즘이 좋아지거나 나빠도 비교 함수 안에 있다."

입력 자료수 n에 따른 함수 유형별 추이