1.2 기술로서의 알고리즘
컴퓨터는 상당히 빠를 수 있지만 ‘무한히’ 빠를수는 없다.
메모리도 매우 저렴할 수 있지만 비용이 ’전혀‘ 들지 않을 수는 없다.
효율성
동일한 문제 해결을 위한 알고리즘이 효율성 면에서 극적으로 다를 수 있다. 하드웨어, 소프트웨어로 인한 차이보다 더 심각할 수 있다.
ex)
- 삽입 정렬 : n개의 값 정렬위해
에 비례하는 시간 걸림(c_1은 n에 독립인 상수). 즉, n^2에 비례함
- 병합 정렬 : \(c_2nlog_2n\) 의 시간 걸림(c2는 n에 독립인 또 다른 상수). 즉, nlog_2(n)
상수는 입력 크기 n에 비해 수행시간에 영향을 훨씬 작게 준다.
두 수의 의 비교 : n이 1000 이면 로그값은 약 10, n이 106 이면 로그값은 약 20
입력 크기가 작을 때 : 보통 삽입 정렬이 빠르다.
n값이 커질수록 n 과 로그값의 차이는 커진다. => c1이 c2보다 아무리 작아도 병합 정렬이 더 빨라지는 교차점이 항상 존재
ex2) 빠른 컴퓨터 A의 초당 100억 개의 명령어 처리
느린 컴퓨터 B의 초당 1000만 개의 명령어 처리
10^7개의 숫자를 A는 삽입 정렬, B는 병합 정렬 한다면?
A
\[2(10^7)^2명령어/10^{10}명령어/초 = 20.000초(5.5시간 이상)\]B
\[50·10^7log_210^7명령어/10^7명령어/초 ≈ 1,163초(20분 미만)\]문제의 크기가 커질수록 병합 정렬의 상대적인 장점도 커진다.
알고리즘과 다른 기술들
알고리즘 : 하나의 기술(하드웨어 처럼)
발전된 컴퓨터 구조와 제조 기술처럼,
사용하기 쉽고 직관적인 그래픽 사용자 인터페이스(GUI)처럼,
객체 지향 시스템처럼,
통합적인 웹 기술처럼,
빠른 유무선 네트워킹처럼
중요하다
