[종만북] 4. 알고리즘의 시간 복잡도 분석 ② (미완)

4. 알고리즘의 시간 복잡도 분석 ② 

4.5 시간 복잡도

시간 복잡도란 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것입니다.

기본적인 연산이라는 것은 사칙연산, 대입, 대소 비교 등을 뜻하며 반복문 같은 것들은 포함하지 않는다.

시간 복잡도가 낮다고 해서 항상 더 빠르게 동작하는 것은 아니다. 입력의 크기가 작고 시간 복잡도가 높은 알고리즘이 입력의 크기가 크고 시간 복잡도가 낮은 알고리즘보다 빠르게 동작할 수 있다.

입력의 종류에 따른 수행 시간의 변화

알고리즘에 따라서, 어떤 입력(배열)이 들어오느냐에 따라 수행 시간이 달라질 수 있다. 만약, 배열에서 주어진 숫자를 찾아서 그 idx 를 반환하는 함수가 있다고 생각했을 때,

• 최선 : 찾는 숫자가 맨 앞에 있을 때, 반복문의 수행 횟수는 1이다.
• 최악 : 배열에 찾는 숫자가 없을 때, 반복문의 수행 횟수는 N이다.
• 평균 : 기대치는 N / 2 이며, 평균적인 반복문의 수행 횟수는 N / 2 이다.

대개 최악과 평균을 쓴다. 이 두 기준이 거의 같기 때문인데, 물론 그렇지 않은 경우도 있다. (quick sort, 랜덤화 알고리즘)

---

.2

1. 

 

2. 

 

3. 

 

4. 

 

5. 

 

6. 

 

 

---

.3

1. 

 

2. 

 

3. 

 

4. 

 

5. 

 

6.