- 알고리즘은 실행시간이 얼마가 걸리는지가 아니라 '데이터의 크기에 따라 얼마나 실행시간이 증가하는지'가 중요
e.g. 전화번호를 각각 binary Search와 simple search 하는 경우의 실행시간을 생각해봅시다.(한번 실행시 1ms가 걸린다고 가정)
| 전화번호갯수 | BinarySearch | Simple Search | 비고 |
|---|---|---|---|
| 1,000 | 약 10ms | 1,000ms | 이정도 차이야 뭐 견딜수있음 |
| 1,000,000,000 | 13ms | 11days | 아... simple search 못쓰겠다... |
- 알고리즘의 속도는 시간이 아니라 연산 횟수가 어떻게 증가하는지로 측정함
- -> 데이터 크기가 커질때 알고리즘의 실행속도가 얼마나 증가하는지 알 수 있음
- 알고리즘의 실행시간은 일반적으로 최악의 실행경우를 가정한 Big O 표기법을 사용함.
- O(n) , O(log n) , O(n*log n), O(n^2)