[자료구조 기초] Binary Search Analysis / 이진 탐색 분석 / 시간복잡도 이해용 예제

이진 탐색(Binary Search)에 대해 알아보자

시간복잡도에 대한 개념을 이해하기 위한 예제

 

이진 탐색(Binary Search) 기능

    - 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘

    - ★ 정렬된 데이터가 아니면 적용이 불가능하다 (Search 전 Sorting이 우선적으로 필요하다)

 

출처) 윤성우의 열혈 자료구조

이진 탐색(Binary Search) 구현

    - 생략

 

이진 탐색(Binary Search) 시간복잡도를 구하는 방법

    - 핵심이 되는 연산이 무엇인지 잘 판단 必

        - 이진 탐색에서는 값을 비교하는 연산자 ==

    - Worst Case

        - Linear Search보다 훨씬 복잡해졌다.

        - 데이터의 수가 n 일때 n / 2, n / 4, n / 8 … 이렇게 비교 연산이 진행되고

        - 마지막 n = 1일 때, 비교 연산을 한 번 더 실행

 

        규칙 발견

        - n이 1이 되까지 2로 나눈 횟수 k회, 비교연산 k회 실행

        - 데이터가 1개 남았을 때, 마지막 비교연산 1회 실행

        - 즉, T(n) = k + 1

 

        k 구하기

        - n 을 2로 k번 나눈다 -> n X (1/2)**k = 1

        - n X (1/2)**k = 1 -> n x 2**-k = 1 -> n = 2**k

        - n = 2**k -> log2(n)=log2(2)**k -> log2(n) = k log2(2) = log2(n) = k

 

        Finally

        - T(n) = k + 1 -> T(n) = log2(n) + 1

        - 데이터 수의 중가에 따른 연산횟수의 변화 정보를 판단하는 것으로 +1 은 생략할 수 있다

        - 즉, T(n) = log2(n)