[알고리즘] 3. 효율적인 알고리즘 개발의 중요성

알고리즘의 효율성은 굉장히 중요하다. 문제를 해결하기 위해 사용할 수 있는 자원이 한정되어 있기 때문이다. 그리고 아무리 자원이 많더라도 알고리즘이 비효율적이면 문제를 제대로 해결하지 못할 수 있다. 완전 탐색과 이진 탐색의 비교를 이용해 알고리즘의 효율성의 중요성을 알아보겠다.

 

---

완전 탐색 대 이진 탐색

완전 탐색 알고리즘

배열의 처음부터 끝까지 원하는 값을 찾는 것이다.

 

이진 탐색 알고리즘

이진 탐색은 정렬된 목록에서 요소의 위치를 ​​찾는 알고리즘이다. 

1. 찾고자 하는 값 x를 배열 중앙의 원소와 비교한다.
   1. 둘이 같으면 문제 해결
2. x가 배열 중앙의 원소보다 작으면 x는 배열의 전반부에 있으므로 배열의 전반부에 대해 똑같은 탐색을 한다. 즉, x를 배열의 전반부의 중앙의 원소와 비교한다.
3. x가 배열 중앙의 원소보다 크면 x는 배열의 후반부에 있으므로 배열의 후반부에 대해 똑같은 탐색을 한다. 즉, x를 배열의 후반부의 중앙의 원소와 비교한다.
4. x를 찾거나 x가 배열에 없다고 결정될 때까지 위 과정을 반복한다.

완전 탐색과 이진 탐색의 비교

완전 탐색은 매번 검사할 때마다 검사해야 하는 요소의 수를 1개 줄인다. 최대 n번의 비교를 수행하여 x가 크기 n의 배열에 있는지 확인한다. x가 배열에 있으면 비교 횟수는 n보다 작다. 배열에 없으면 비교 횟수는 n이다. T(n) = O(n)

이진 탐색은 매번 검사해야 하는 요소의 수를 반 줄인다. T(n) = O(logn)

이진 탐색이 완전 탐색보다 훨씬 더 효율적인 것으로 보인다. 다만 단점으로 정렬이 되어 있는 데이터에만 쓸 수 있다.