In this post, 01 Algorithm lecture is introuduced.

CLRS chapter 1의 내용을 다룬다.

Math vs CS

math 와 CS의 차이는 computability 이다.

Data Structure vs Algorithm

자료구조에서 엄밀한 증명을 다루지 않았다면 알고리즘에서는 컴퓨터가 계산 가능한 방법으로 증명해야 하는 것이 매우 중요한 작업이다. time complexity, algorithm의 correctness 증명 과정에서 computability 가 핵심 요소이다.

Algorithm with Computer Architecure

quick sort 의 worst case 시간 복잡도는 \(O(n^2)\) 인 반면, merge sort 는 O(nlogn) 이다. 그런데 왜 quick 이라는 말은 시간 복잡도가 더 큰 quick sort에 붙을까.

quick sort는 in-place algorithm 인 반면, merge sort는 새로운 array를 생성하는 등 in-place algorithm이 아니기 때문에 page fault 가 일어날 확률이 높다. 때문에 아무리 시간 복잡도가 유리한 알고리즘을 만들더라도 memory와 disk를 계속 오가게 되면 시간 복잡도는 무의미해진다. 알고리즘을 공부할 때 컴퓨터 구조, OS에 대한 이해가 바탕이 되어야 하는 이유이다.