▼ 표 2-1 복잡도가 성능에 미치는 영향
|
검색 알고리즘 |
복잡도 |
60개 행 중 레코드를 찾는 데 걸리는 시간 |
|
리사의 삼촌 차고에 있는 DIY 양자 컴퓨터 |
O(1) |
1초 |
|
이진 검색 |
O(log N) |
6초 |
|
선형 검색(프레젠테이션 한 시간 전에 상사가 부탁했다.) |
O(N) |
60초 |
|
인턴이 실수로 for 루프 두 개를 중첩해서 넣었다. |
O(N2) |
1시간 |
|
스택 오버플로에서 무작위로 가져온 일부 코드 중에는 검색하면서 중간에 체스 문제를 푸는 코드가 있다. 하지만 개발자가 이 부분을 삭제하지 않았다. |
O(2n) |
365억 년 |
|
이 알고리즘은 실제 레코드를 찾는 대신 우리가 원하는 특정한 순서로 레코드들을 정렬하기 위한 배열을 찾으려고 한다. 좋은 소식이 하나 있다면, 이 개발자는 더 이상 여기서 일하지 않는다. |
O(N!) |
이 우주가 끝날 때까지 |