알고리즘 성능 분석법

윤성우의 열혈 자료구조에선 알고리즘 성능 분석에대해 간략하게 설명했다. 그를 토대로 공부했다.

사실 2학년때 배운 내용이라 그것도 이지영교수님께 좀 깊게 공부한 이력이있어 그렇게 무리는 없었지만 저자가 이 개념을 처음 접하는 사람들을 위해 엄청나게 쉽고 자세하게 설명해줬구나 하는 걸 느꼈다. 의식의 흐름대로 쓰면서 짜임새와 정확성을 잃지 않은것이 글을 정말 잘 쓴다고 느꼈다.

 

알고리즘 성능은 두가지로 평가한다고 한다. 시간복잡도와 공간복잡도, (time complexity, space complexity)

시간복잡도의 경우 빅오(O)를 사용하여 많이 판별하는데 최악의 경우를 기준으로 잡아 그 식의 빅오를 이용한다.

 

빅오란 뭘까.

정의를 보면 함수 f(n)과 g(n)이 주어졌을때 K이상의 n에 한해 f(n)<=Cg(n)를 만족시키는 K,C가 존재한다면 g(n)을 f(n)의 빅오 라고 한다.

 

난 이 정의가 마음에 든다. 빅오에대해 너무도 깔끔하게 한 문장으로 잘 설명해 줬다고 생각한다.

 

오랜만에 순차검색알고리즘이랑 이진검색 알고리즘을 구현해봤는데 생각보다 코딩이 죽진 않은것같다. 한자도 못칠줄알았는데 막상앉으니 좀 버벅거려도 코딩은됐다. 군에서 다 까먹는건 아니구나.

 

공간 복잡도에대해선 책에서 그냥 넘어간것같지만 한번 찾아보았다.

공간복잡도 계산법은 대충 고정 메모리값에 사용되는 인스턴스,변수의 갯수혹은 크기를 합한것으로 보인다.

 

그러니까 최고의 알고리즘은 최적의 시간복잡도와 공간복잡도를 가지는것인데 이는 너무 이상적인 조건이라고 한다.