#3 자료구조 <시간복잡도> Big-Oh Big-Omega Big-Theta

<알고리즘의 분석>

알고리즘의 성능을 나타낼때 정확성, 복잡도, 효율성이 대상이 됩니다.

알고리즘의 복잡도란 알고리즘의 성능을 나타내는 지표입니다.

알고리즘의 수행시간 -> 시간 복잡도 (time complexity)

알고리즘의 사용공간 ->공간 복잡도 (space complexity)

주로 시간복잡도로 알고리즘의 성능을 평가합니다.

<알고리즘의 복잡도 분석>

시간 복잡도 측정 방법

1.Big-Oh

O(n)은 수행시간 함수 입니다.

f(n) = 2n^2 + 3n + 5이면, 양의 상수 c 값을 최고 차항의 계수인 2보다 큰 4를 택하고 g(n) = n^2으로 정하면, 3보다 큰 모든n에 대해 2n^2 + 3n + 5 < 4n^2이 성립, 즉, f(n) = O(n^2) f(n)의 수행시간은 O(n^2)라는 것입니다.

흔히 수행시간에서 계수는 생략가능합니다.

물론 2n^2 + 3n + 5 = O(n^3)도 성립하고, 2n^2 + 3n + 5 = O(2^n)도 성립한다. 그러나 g(n)을 선택할 때에는 정의를 만족하는 가장 차수가 낮은 함수를 선택하는 것이 바람직함

주어진 수행시간의 다항식에 대해 O-표기를 찾기 위해 간단한 방법은 다항식에서 최고 차수 항만을 취한 뒤, 그 항의 계수를 제거하여 g(n)을 정한다. 

2. Big-Omega notation  

N0이상 값에서 f(n)값이 cg(n)값이 항상 크다면 g(n)이 f(n)의 하한입니다.

3.Big-Theta notation

결론적으로 차수가 낮을 수록 증가율이 적으니까 좋다고 할 수 있습니다.

<왜 증가율이 중요한가?>

-점근적 표기법이 증가율을 결정한다

-입력의 크기가 증가하면 알고리즘의 수행시간이 얼마나 빠르게 증가하는지를 알 수 있다

-충분히 큰 입력을 다루는 알고리즘에서는 증가율이 작은 알고리즘이 보다 효율적이다

-같은 문제를 다루는 두개 이상의 알고리즘 중에서 증가율이 작은 알고리즘을 선택할 수 있다