[알고리즘]Best Conceivable Runtime(BCR)

Date: 2024.08.25 Updated: 2024.08.25

카테고리: Algorithm

What is the BCR?

Best Conceivable Runtime(BCR)은 주어진 문제에서 최상의 경우를 가정했을 때, 알고리즘이 달성할 수 있는 이론적인 최적의 실행 시간을 의미한다. BCR은 문제 자체의 복잡도에 의해 결정되며, 알고리즘 설계자가 이를 기준으로 알고리즘의 효율성을 평가하고 최적화할 수 있는 기준점을 제공한다.

How to Use BCR

Best Conceivable Runtime(BCR)은 주어진 문제의 최적의 실행 시간을 정의하며, 알고리즘 최적화를 위한 목표점을 설정하는 데 유용하다. BCR에 도달할 때까지는 시간 복잡도와 공간 복잡도를 개선할 수 있지만, BCR에 도달한 이후에는 더 이상의 시간 복잡도 개선이 불가능하다는 것을 의미한다. 대신, 추가적인 공간 최적화에 집중할 수 있다. BCR은 알고리즘 설계 과정에서 최적의 경로를 찾고 불필요한 작업을 줄이는 데 중요한 역할을 한다.

Example Problem Python Code with BCR

문제: 두 개의 정렬된 배열에서 공통 원소의 개수를 찾기.

배열 A와 B는 정렬되어 있으며, 동일한 길이와 모두 고유한 요소를 가진다.
목표: 두 배열의 공통 요소의 수를 찾는다.

1) Brute Force Approach

가장 단순한 방법은 모든 요소를 비교하는 것이다. 하지만 이 방법은 매우 비효율적이다. Brute force의 시간 복잡도는 \(O(N^2)\)으로 매우 비효율적이다.

def count_common_elements_brute_force(A, B):
    count = 0
    for a in A:
        for b in B:
            if a == b:
                count += 1
    return count

A = [13, 27, 35, 40, 49, 55, 59]
B = [17, 35, 39, 40, 55, 58, 60]
cnt = count_common_elements_brute_force(A, B)
print("Count: {}".format(cnt)) # Count: 3

2) Improved Algorithm using Binary Search

정렬된 배열을 이용하여 이진 탐색을 수행하면, 비교를 보다 빠르게 할 수 있다. 각 요소에 대해 이진 탐색을 수행하므로 \(O(N \log N)\)의 시간 복잡도를 가진다.

def binary_search(arr, x):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == x:
            return True
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return False

def count_common_elements_binary_search(A, B):
    count = 0
    for element in A:
        if binary_search(B, element):
            count += 1
    return count

A = [13, 27, 35, 40, 49, 55, 59]
B = [17, 35, 39, 40, 55, 58, 60]
cnt = count_common_elements_binary_search(A, B)
print(f"Count: {cnt}") # Count: 3

3) Optimal Algorithm using Hash Table

정렬된 배열의 특성을 활용하여 하나의 배열을 해시 테이블로 변환하고, 다른 배열의 요소를 상수 시간 \(O(1)\)에 검색할 수 있다. 이는 최적의 시간 복잡도인 \(O(N)\)을 달성하며, 추가적인 공간 복잡도를 필요로 한다.

def count_common_elements_hash_table(A, B):
    hash_table = set(B)  # O(N)
    count = 0
    for element in A:  # O(N)
        if element in hash_table:  # O(1)
            count += 1
    return count

A = [13, 27, 35, 40, 49, 55, 59]
B = [17, 35, 39, 40, 55, 58, 60]
cnt = count_common_elements_hash_table(A, B)
print(f"Count: {cnt}") # Count: 3

4) Optimal Algorithm with Minimal Space

공간 복잡도를 줄이기 위해 추가적인 자료 구조 없이, 두 개의 포인터를 이용한 선형 탐색(Linear Search)을 사용한다. 이는 두 정렬된 배열을 병합하는 과정과 유사하며, 공간 복잡도 \(O(1)\)로 최적의 시간 복잡도 \(O(N)\)을 유지한다.

def count_common_elements_optimal(A, B):
    i, j = 0, 0
    count = 0

    while i < len(A) and j < len(B):
        if A[i] == B[j]:
            count += 1
            i += 1
            j += 1
        elif A[i] < B[j]:
            i += 1
        else:
            j += 1

    return count

A = [13, 27, 35, 40, 49, 55, 59]
B = [17, 35, 39, 40, 55, 58, 60]
cnt = count_common_elements_optimal(A, B)
print(f"Count: {cnt}") # Count: 3

Summary

최종 분석
- Brute Force: \(O(N^2)\) - 최악의 방법.
- Improved Algorithm: \(O(N log N)\) - 더 나은 방법이지만 최적은 아님.
- Optimal Algorithm (Hash Table): \(O(N)\) 시간, \(O(N)\) 공간 - 최적의 시간 복잡도, 추가 공간 필요.
- Optimal Algorithm (Two-pointer): \(O(N)\) 시간, \(O(1)\) 공간 - 최적의 시간 및 공간 복잡도.

Meaningful