Week1-2 Asymptotic Analysis

Asymptotic Analysis : 점근적 분석

 

점근적분석은 어떤 알고리즘에 큰 입력 데이터셋을 적용할 때, 알고리즘의 제한 동작과 성능을 설명하기 위한 방법이다.

즉, N이 무한대로 수렴한다고 가정하고 생각하면 편하다.

Time Complexity and Space Complexity : 시간 복잡도와 공간 복잡도 

좋은 알고리즘이란 ? 작은 메모리공간, 적은 시간 내에 주어진 임무를 제대로 수행하는 알고리즘이 좋은 알고리즘이다.

알고리즘을 평가할 때, 수행시간과 메모리 사용량을 평가기준으로 둔다. 

이 각각에 해당하는 사항이 시간복잡도와 공간복잡도이다.

 

 

시간복잡도 : 알고리즘의 수행시간의 분석 결과

공간복잡도 : 알고리즘의 메모리 사용량에 대한 분석 결과 

 

알고리즘의 시간복잡도는 연산의 횟수를 세고 처리해야할 데이터의 수에 대한 연산횟수의 함수를 만들어서 계산한다.

 연산횟수의 카운팅은 다음과 같이 세가지 경우로 나누어 생각한다

1. 최선의 경우 (Best Case)
2. 최악의 경우 (Worst Case)
3. 평균적인 경우 (Average Case)

여기서 가장 중요한것은 최악의 경우이다. 알고리즘의 성능은 최악의 경우를 생각해서 판단해야한다. 

---

이해해기 쉽게 시간복잡도의 예시를 들어보자.

 

n개의 랜덤한 정수가 지정된 크기가 n인 배열에서, 가장 큰 정수를 찾기위해 몇번의 연산을 수행하는가?

가장 첫번째 0번째 인덱스를 max라고 두고, 나머지 n-1개의 배열들과 우리는 n-1번 비교할것이다. 

따라서, 이 경우, 임의의 n개의 정수가 들어간 n개의 배열에서 가장 큰 정수를 찾을떄의 Time Complexity는 N-1이라고 볼 수 있다.