알고리즘 문제 해결 전략 4.6 수행 시간 어림짐작하기

book.algospot.com/estimation.html

알고리즘 문제 해결 전략

"입력의 최대 크기와 알고리즘의 시간 복잡도를 보고 수행 시간을 어림짐작할 수 있어야 합니다."

 

"프로그램의 동작 속도에 영향을 끼치는 요소는 입력의 크기와 시간 복잡도를 제외하고도 엄청나게 많기 때문입니다. CPU의 클록 속도, 1클록마다 수행 할 수 있는 CPU 명령어의 수, 프로그램의 메모리 접근 패턴, 운영 체제와 컴파일러의 버전, ..., 목록을 만들자면 끝이 없습니다."

 

"그러나 많은 경우에는 시간 복잡도와 입력 크기만 알고 있더라도 어떤 알고리즘이 시간 안에 동작할지 대략적으로 짐작하는 것이 가능합니다."

 

"시간이 많이 걸리는 연산(실수 연산, 파일 입출력)을 많이 사용할 경우에는 이 가정보다 시간이 오래 걸릴 수밖에 없지요. 

 

"현대의 CPU는 메모리에 있는 자료를 직접 접근하는 대신 캐시라고 부르는 작고 빠른 메로리로 옮겨온 뒤 처리합니다. 메모리에서 캐시로 자료를 가져올 때는 인접한 자료들을 함께 가져오기 때문에, 인접한 자료들을 연속해서 사용하는 프로그램은 메모리에서 매번 자료를 가져올 필요 없이 캐시에 이미 저장된 자료를 사용하게 됩니다. 이런 차이는 시간 복잡도에는 아무 영향을 미치지 않지만 프로그램의 실제 수행 속도는 훨씬 빨라지게 됩니다."

 

"1초 안에 처리할 수 있는 최대 입력 크기가 각 알고리즘에 따라 어떻게 변하는지 살펴봅시다."

 

"특히 중요한 것은 주먹구구 법칙으로 예측한 것보다 느리게 동작하는 프로그램은 없었다는 점입니다. 1억이라는 기준은 가능한 보수적으로 정한 것이기 때문에 이 현상은 바람직한 것입니다."

 

"실험 환경은 인텔 코어 i7 920(네할렘), g++4.4.3, 우분투 리눅스 10.04입니다."