이진 탐색 알고리즘 역시 시간복잡도를 알아보고자 한다. 그리고 이전에 알아본 순차 탐색 알고리즘에 비해 얼마나 효율적인지도 시간복잡도를 통해 알아본다. 여기서 알아볼 시간복잡도는 최악의 경우만을 따진다. 최선의 경우는 한 번이고, 평균적인 경우는 따지기가 몹시 애매하기 때문이다. 아니, 솔직히 말하면 그냥 어려워서다. 나중에 알아보도록 하자. 여기선 오직 최악의 경우(Worst case)만을 다루도록 하겠다. 최악의 경우(Worst case) 시간복잡도 데이터의 개수가 n개인 경우, 이진 탐색 알고리즘을 이용했을 때의 연산 경우의 수는 아래와 같이 일반화할 수 있다. 1. n이 1이 되기까지 2로 나누고 나머지를 버린다. 비교연산 횟수 총 k회 2. n이 1이 되었을 때, 마지막 비교연산 1회 이제 k를..
이전에 설명한 순차 탐색 알고리즘보다 훨씬 좋은 성능을 보이는 이진 탐색(이분 탐색) 알고리즘이다. 영어로는 Binary Search Algorithm. 뜻에서 알 수 있듯이 숫자 2와 관련있는 알고리즘이다. 탐색 범위를 반 씩 줄여가며 탐색하기 때문에 이런 이름이 붙혀졌다. 다만 이 알고리즘은 한 가지 제약조건이 있다. 조건 : 저장된 데이터는 정렬되어 있어야 한다! 성능이 빠른데에는 역시 그만한 이유가 있다. 그렇다면 이제 간단한 원리에 대해 알아보자. 원리 탐색에는 언제나 지시자가 존재하는데, 이진 탐색의 경우에는 first, last, mid 3가지의 지시자가 존재한다. 위의 이미지처럼 7개의 데이터가 담긴 오름차순으로 정렬된 데이터에서 숫자 '3'을 탐색한다고 가정해보자. 첫 번재 탐색에서는 위..
바로 이전에 순차 탐색 알고리즘에 대해서 깊게 탐구해보았다. 그러나 평균 시간 복잡도를 좀 더 제대로 확인할 수 있는 방법을 생각해보았다. 내가 구한 공식과 실제 값을 비교해볼 수 있는 프로그램을 구현하는 것이다. 그래서 해당 코드를 직접 수정하여, 예측값과 10000번의 테스트를 통해 얻은 실제 평균값을 비교하는 것이다. 배열 내에 값이 존재할 확률(p)는 50%로 설정해두었다. 구현 #include #include #include #include #include using namespace std; int LinearSearch(vector x, int target) { for (int i = 0; i < x.size(); i++) if (x[i] == target) return i; return -..
순차 탐색 알고리즘은 탐색 알고리즘의 하나다. 다양한 알고리즘들 중에서도 가장 간단한 알고리즘이라고 할 수 있다. 먼저 벡터와 함수를 활용하여 코드를 구현해보자. 구현 #include #include #include #include using namespace std; int LinearSearch(vector x, int target) { for (int i = 0; i < x.size(); i++) if (x[i] == target) return i; return -1; } int main() { vector v(10); for (int i = 0; i < 10; i++) { v[i] = i; cout
