이진 탐색 시간 분석하기: 효율적인 탐색 알고리즘의 성능 측정[파이썬]

 

이진 탐색(Binary Search)은 정렬된 배열에서 중간 요소를 기준으로 탐색 범위를 절반으로 줄여가며 목표 값을 찾는 효율적인 알고리즘입니다.

이진 탐색의 시간 복잡도는 O(log n)으로, 데이터가 많아질수록 선형 탐색보다 훨씬 빠른 성능을 보여줍니다.

1. 이진 탐색 시간 분석을 위한 Python 코드

아래 파이썬 코드는 이진 탐색을 구현하고, 배열 크기를 변경하면서 탐색에 걸리는 시간을 측정하는 코드입니다.

이 코드는 선형 탐색과 마찬가지로 배열의 크기가 커질 때 이진 탐색의 성능이 어떻게 변하는지를 분석합니다.

import time
import random

# 이진 탐색 함수 (재귀적 구현)
def binary_search(arr, target, low, high):
    if low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            return binary_search(arr, target, mid + 1, high)
        else:
            return binary_search(arr, target, low, mid - 1)
    else:
        return -1

# 배열 크기를 변경하며 이진 탐색 시간 측정
def measure_time_binary_search():
    sizes = [1000, 5000, 10000, 50000, 100000, 500000, 1000000]  # 배열 크기
    results = []

    for size in sizes:
        # 정렬된 랜덤한 배열 생성
        arr = sorted(random.sample(range(size * 10), size))
        target = arr[-1]  # 마지막 요소를 찾도록 설정 (최악의 경우)

        # 시간 측정 시작
        start_time = time.time()
        
        # 이진 탐색 실행
        binary_search(arr, target, 0, len(arr) - 1)
        
        # 시간 측정 종료
        end_time = time.time()
        
        # 걸린 시간 계산
        elapsed_time = end_time - start_time
        results.append((size, elapsed_time))

    return results

# 이진 탐색 시간 측정 결과 출력
binary_search_times = measure_time_binary_search()
for size, elapsed_time in binary_search_times:
    print(f"Array Size: {size}, Time Taken: {elapsed_time:.10f} seconds")

2. 코드 설명

1. binary_search 함수: 이진 탐색을 재귀적으로 구현합니다. 중간 인덱스를 계산한 후, 중간 값이 목표 값보다 크거나 작으면 탐색 범위를 절반으로 줄여 나갑니다.
2. measure_time_binary_search 함수: 배열 크기를 변경하면서 이진 탐색에 걸리는 시간을 측정하는 함수입니다. 배열 크기가 커질 때 이진 탐색이 얼마나 빠르게 동작하는지를 보여줍니다.
3. 배열 생성 및 타겟 설정: 랜덤한 숫자로 채워진 배열을 정렬한 후, 배열의 마지막 요소를 목표 값으로 설정합니다. 이 경우 이진 탐색의 최악의 경우를 시뮬레이션합니다.
4. 시간 측정: time.time() 함수를 사용하여 이진 탐색이 시작되기 전과 후의 시간을 기록하고, 걸린 시간을 계산합니다.

3. 예상 결과

 

이진 탐색은 O(log n)의 시간 복잡도를 가지기 때문에, 배열 크기가 커져도 탐색 시간이 크게 증가하지 않습니다.

예를 들어, 배열 크기가 1,000에서 1,000,000으로 증가해도 시간 증가폭이 선형 탐색보다 훨씬 작을 것입니다.

 

코드를 실행하면 각 배열 크기에 따른 탐색 시간이 출력되며, 이진 탐색이 매우 효율적인 알고리즘임을 확인할 수 있습니다.

공감과 댓글은 저에게 큰 힘이 됩니다.

Starting Google Play App Distribution! "Tester Share" for Recruiting 20 Testers for a Closed Test.

Tester Share [테스터쉐어] - Google Play 앱