[CLRS] [2-2] Analyzing algorithms

1.  Introduction

- 알고리즘을 분석하는 것은 알고리즘이 요구하는 자원을 예측하는 것을 의미

- 여기서 말하는 자원은 메모리와 시간을 의미함

- 문제에 대한 여러 후보 알고리즘을 분석하면 가장 효율적인 것을 선택할 수 있게 된다.

- 사용가능한 Candidate가 하나 이상 있을 수 있지만, 분석하는 과정에서 쓸모없는 알고리즘을 소거할 수 있다.

 

2. RAM(Random-Access Machine)

- 사용자가 자유롭게 내용을 읽고 쓰고 지울 수 있는 기억장치

- 컴퓨터가 켜지는 순간부터 CPU는 연산을 하고 동작에 필요한 모든 내용이 전원이 유지되는 내내 이 RAM에 저장된다.

- RAM은 명령어들이 하나씩 순차적으로 실행되며, 동시에 두작업 이상을 할 수 없다라고 가정한다. 

 

3. Analysis of insertion sort

- 2-1 에서 구현한 Insertion sort(삽입 정렬)은 얼마나 오래 걸릴까?

- 이를 알아내기 위해선 컴퓨터에서 실행해보고 소요 시간을 측정해야 함

- 하지만 실행 시간은 환경에 따라서 달라지기 때문에 알고리즘 자체를 분석하여 시간을 계산하여야 함

- 이땐 각 코드 한줄 한줄을 기준으로 실행횟수를 바탕으로 계산하게 된다. 

 

# 주석 : cost을 0으로 취급한다. 

- 이를 수식으로 나타내면 다음과 같다. 

 

- 만약 INPUT으로 들어오는 배열이 최상의 상태로 정렬이 되어 있는 상태라면 ti = 1이되고, 실행시간은 다음과 같이 계산된다.

 

- 따라서 실행 시간은 'n'의 선형 함수로 구성되어 있음을 알 수 있다.

 

- 만약 INPUT으로 들어오는 배열이 최악의 상태로 정렬되어 있다면 어떨까? 즉, 배열이 내림차순으로 정렬되어 있음을 의미한다.

- i = 2,3,4,...n 일 때, ti = i 가 된다. 

- 즉, 실행시간은 n^2의 함수라는 것을 알 수 있다. 

- 

4. 최악의 경우를 분석

- 우리는 앞으로 프로그램의 성능을 계산할 때 최악의 실행시간에만 집중할 것이다. 

- 그 이유는 다음과 같이 2가지 이유가 있다.

1) 알고리즘의 최악의 실행 시간을 알면 그 이상 오래 걸리지 않는다는 보장이 생긴다.

2) 최악의 경우가 실생활에 자주 발생함 --> "DB에 존재하지 않은 정보를 이용할 때"

- 추가적으로 실행시간을 나타낼 때 우리는 최고차항의 차수만 나타낼것이다(계수 == 1)

 - T(n) = 3n^2+3 --> Θ(n^2)

cf) 이를 Θ Notation 이라고 한다. 

 

5. Exercises

Q1)

--> Θ(n^3)