Algorithms Chapter 1 (part2)

오늘은 알고리즘의 효율성 분석에 대해 알아보자

 

 

 

알고리즘의 효율성 분석은 시간 복잡도 함수로 나타낸다.

f(n)의 BigO를 본다.

 

모든 알고리즘 input이 커질수록 시간이 커진다.

효율성을 나타낼 때 그 알고리즘에 실행에 걸리는 시간을 input 사이즈에 대한 함수로 나타낸다.

n = input 사이즈 ,f(n) = 걸리는 시간

 

 

 

input size가 중요하지만 다음에 설명하겠다.

 

 

시간 복잡도의 분석을 time complexity analysis라고 한다.

 

 

T(n)은 걸리는 시간이다.

input 사이즈에 대해 걸리는 시간.

 

시간 복잡도 함수 : time complexity function

input size가 같은 인스턴스라도 걸리는 시간이 다를 수 있다.

예를 들어 버블 sort를 보면 순서가 굉장히 헝클어져 있으면 시간이 오래 걸리고 아니면 안 걸릴 수도 있다.

 

T(n)에 관한 것이 n에 관한 함수라고 했는데

n값이 같으면 결과 값이 같아야 되는데 그렇지가 않다는 것이다.

 

그러면 어떻게 결정하냐?

가장 오래 걸리는 경우를 T(n)으로 정의한다.

최악의 경우를.

 

 

이건 너무 친절한 설명이고 그다지 중요한 개념이 아니다.

표준용어가 아니므로 넘어가겠다.

 

 

가장 시간이 오래 걸리는 경우를 worst-case time complexity라고 한다.

특별히 이런걸 강요하기 위해 W(n)이라고 쓰지만 보통 T(n)이라고 쓴다.

그렇게 중요한 개념은 아니다.

 

우리가 찾는 배열이 맨 끝에 있을 때.

 

그냥 최악의 경우를 time complexity라고 한다 이게 전부다.

 

 

평균 시간 복잡도도 중요하다.

average time complexity가 worst time complexisty보다 더 중요할 수 있다.

알고리즘의 배경에 따라 달라질 수 있다.

따라서 둘 다 분석하는게 제일 좋다.

그런데 짐작하겠지만 average time complexity 분석이 더 어렵다.

 

 

찾는게 처음에 있으면 한 번 비교할거고 맨 뒤에 있으면 제일 나중에 비교할거고..

n으로 나누었다는 것이 무엇을 뜻하느냐?

각각의 찾을 확률이 1/n로 같다고 가정하는 것이다.

확률 x 그 경우의 값

uniform distribution이라고 가정하고 평균시간을 구하는 것이 대부분이다.

 

단지 샘플을 말하고자 하는거지 개념을 말하고자 하는것이 아니다.

 

 

최선의 경우의 시간 복잡도.

최선의 경우에 얼마나 걸리느냐 : 큰 의미는 없다.

요행을 바라는 거니까.

 

 

 

space complexity : 공간복잡도를 분석하는 것

메모리를 얼마나 쓰느냐 를 분석하는 것이다.

메모리가 작을 때 쓴다.

요즘은 메모리가 흔해서 막 그렇게 중요하진 않다.

대개의 복잡도는 시간복잡도를 말한다.

 

그러나 알고리즘을 효율성을 따지기 전에 정확성을 먼저 따져야 한다.

모두다 정확하게 쏠루션을 구해야지 알고리즘이라고 할 수 있기 때문이다.

다 푸는데 한가지 인스턴스를 못 푼다? 그것은 알고리즘이 아니다.

이런 걸 correctness analysis라고 한다.

그런데 매번 하진 않는다.

왜냐면 자명하기 때문이다.

 

그래서 Analysis를 크게 두개로 나누면

correctness 와 efficiency로 나눌 수 있다.