점근적 분석, 점근적 표기법, 시간 복잡도, 공간 복잡도

시간 복잡도

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

 

공간 복잡도

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

 

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

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

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

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

 

점근적 분석이란

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

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

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

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

 

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

 

 

 

---

 

 

알고리즘의 실행 시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존합니다. 이 속도는 컴퓨터의 처리속도, 사용된 언어 종류, 프로그래밍 언어를 컴퓨터가 실행할 수 있는 코드로 바꾸는 컴파일러의 속도 등에 달려있습니다.

 

알고리즘의 실행 시간에 대해 두 부분으로 나누어 생각해 봅시다.

 

우선, 입력값의 크기에 따른 알고리즘의 실행 시간을 알아야 합니다. 이건 직관적으로 이해가 될겁니다. 배열의 크기가 커지면 선형 검색과 이진 검색의 최대 추측 횟수가 함께 증가한다는 사실은 이미 확인했습니다. GPS를 생각해 봅시다. GPS가 만일 모든 골목길이 아니라 고속도로만 찾으면 길을 훨씬 금방 찾을 수 있을겁니다. 이처럼 입력값의 크기에 대한 함수 로 알고리즘 실행 시간을 생각할 수 있습니다.

 

 

두 번째는 입력값의 크기에 따라 이 함수가 얼마나 빨리 커지는지 알아보는 것입니다. 이것은 실행 시간의 성장률(rate of growth)이라고 부릅니다. 프로그램을 쉽게 유지할 수 있도록 불필요한 부분은 버리고 가장 중요한 부분만 추려내서 함수를 간소화해야 합니다. 

 

 

중요하지 않은 항과 상수 계수를 제거하면 이해를 방해하는 불필요한 부분이 없어져서 알고리즘의 실행 시간에서 중요한 부분인 성장률에 집중할 수 있습니다. 상수 계수와 중요하지 않은 항목을 제거한 것은 점근적 표기법(asymptotic notation)이라 합니다. 이제 점근적 표기법의 세 가지 형태를 살펴봅시다. 바로 big-Θ 표기법, big-O 표기법, 그리고 big-Ω 표기법입니다.

 

 

---

 

 

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에 따른 함수 유형별 추이

 

 

 

 

출처: https://otrodevym.tistory.com/entry/점근적-분석과-표기법-시간-복잡도와-공간-복잡도

점근적 표기법 (개념 이해하기) | 알고리즘 | Khan Academy