연습문제 21-1

빅오 표기법에 대해서 위키피디아에서 읽어보고(http://en.wikipedia.org/wiki/Big_O_notation) 다음 질문에 답해보자.

1. n3+n2의 증가 기준은 무엇인가? 1000000n3+n2의 증가 기준은? n3+1000000n2의 증가 기준은?

2. (n2+n)·(n+1)의 증가 기준은 무엇인가? 곱셈을 시작하기 전에 증가 기준에는 최고차항만 필요하다는 것을 기억하라.

3. f가 O(g)에 있고, g는 미정의 함수라고 한다면 af+b의 증가 기준은?

4. f1과 f2가 O(g)에 있다면 f1 + f2의 증가 기준은?

5. f1은 O(g)에 있고, f2는 O(h)에 있다면 f1 + f2의 증가 기준은?

6. f1은 O(g)에 있고, g2는 O(h)에 있다면 f1·f2의 증가 기준은?

성능을 중시하는 프로그래머는 이러한 분석을 납득하기 어려울 것이다. 이들의 주장도 일리가 있다. 때때로 계수와 비최고차항이 실제 차이를 만들어낸다. 때로는 하드웨어의 사양, 프로그래밍 언어, 입력의 특징이 큰 차이를 내기도 한다. 또한, 작은 문제에 대해서 점진적인 동작은 적합하지 않다.

그러나 이러한 결점을 염두에 두더라도 알고리즘 분석은 유용한 도구다. 적어도 큰 문제에 대해서는 “더 나은” 알고리즘이 일반적으로 더 나은 성능을 보여주며, 때로는 훨씬 더 나은 성능을 보여준다. 같은 상정 기준에 있는 두 알고리즘의 차이는 일반적으로 상수 계수지만, 좋은 알고리즘과 나쁜 알고리즘 사이의 차이는 끝이 없다.