ThePragmaticProgrammer는 ComputerProgramming하면서 항상 자신의 Algorithm을 EstimateToAvoidSurprises한다. 프로그래밍하면서 다음의 경우를 만나면, 대개 이들의 TimeComplexity는 다음과 같다.
circumstance |
example |
|
simple loops |
O(n) |
exhaustive searches, finding the maximum value, generating checksums |
nested loops |
O(n2) |
|
binary chop |
O(log(n)) |
binary search of a sorted list, traversing a BinaryTree, finding the first set bit in a machin word |
O(n log(n) |
||
combinatoric |
O(Cn) |
실전에 있어서,
어떤 TimeComplexity인지 모르겠으면, 실제 값을 넣어보고 그림그려본다.
O(n2)을 갖는 문제들은 고민해보면, DivideAndConquer를 써서 O(n log(n))으로 줄일 수 있는 경우가 있다.
그러나 빠른 Algorithm이 항상 좋은 것은 아니다. 작성/Debugging하기 용이한것이 중요할 수 도 있다. 문제의 성격에 맞는 방법이 필요하다.