Warning (by Knuth)

(1) “slight increase” in one of the parameters of backtracking routine might slow down the total running time by a factor of a thousand.

(2) “minor improvement” to algorithm might cause a hundredfold improvement in speed.

(3) “a sophisticated major improvement” might actually make the program ten times slower.

3번 같은 경우는, 2개 이상의 조건이 조합이 될 때 각 조건이 개선하는 알고리즘의 부분이 disjoint 하지 않다면 overall improvement 가 작을 수 있다는 의미입니다.

좌박사님 수업의 설명에 따르면, 예전에 Knuth 가 공부할 때는 한번 머신에 펀치 뚫은 카드 넣고 한참 기다리고, 또 넣어보고 한참 기다리고 해야했기 때문에 이런 overall 한 가이드라인 정도의 내용도 논문으로 나올 수 있었다고 하네요. (또 사실 저자가 Knuth 인 이유도 있었을거라고 함;;)