데이터 구조 및 알고리즘 심층 분석: Big O 표기법

필자는 데이터 구조와 다양한 유형에 대해 간략하게 소개했습니다. 이 기사에서는 알고리즘의 효율성을 분석하는 방법에 대해 자세히 설명합니다.

이진 검색

이진 검색은 입력이 정렬된 요소 목록인 알고리즘입니다. 사전에서 M으로 시작하는 단어를 검색한다고 가정합니다. 처음부터 시작하여 M에 도달할 때까지 계속 뒤집을 수 있습니다. 그러나 이것은 나쁜 접근 방식입니다. 중간 근처에서 시작하는 것이 더 의미가 있습니다.
이진 검색에서 찾고 있는 요소가 목록에 있으면 위치를 반환하고 그렇지 않으면 없음을 반환합니다. 이진 검색은 목록이 정렬된 경우에만 작동합니다.

파이썬에서 이진 검색을 구현하자

binary_search 함수는 정렬된 배열 숫자와 항목을 사용합니다.

def binary_search(nums, item):

항목이 배열에 있으면 함수는 해당 항목의 위치를 ​​반환합니다. 검색해야 하는 배열 부분을 추적하려면 배열의 아래쪽 부분에는 low를 사용하고 배열의 위쪽 부분에는 high를 사용합니다.

low = 0
high = len(nums) - 1

하나의 요소로 좁히지 않은 동안 중간 요소를 확인하십시오.

while low <= high:
        mid = (low + high) // 2
        guess = nums[mid]

추측이 항목과 같으면 인덱스가 반환됩니다. 추측이 너무 낮으면 그에 따라 낮게 업데이트하고 너무 높으면 높게 업데이트합니다.

 if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return None

전체 코드:

def binary_search(nums, item):
    low = 0
    high = len(nums) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = nums[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return None

nums = [20, 38, 74, 90, 98, 110]
print(binary_search(nums, 98))
print(binary_search(nums, 22))

이제 코드를 실행해보자

$ python3 binary_search.py   
4
None

첫 번째 명령문은 98이 목록의 인덱스 4에 있으므로 4를 반환하고 두 번째 명령문은 22가 목록에 없기 때문에 None을 반환합니다.

시간을 실행
알고리즘의 실행 시간은 입력 크기에 따라 증가하지만 동일한 크기의 다른 입력에 따라 다를 수 있습니다. 이진 검색은 대수 시간으로 실행됩니다. 목록에 128개의 이름이 있으면 최대 단계 수는 7입니다(2 pow 7은 128).

빅오 표기법

Big O 표기법은 알고리즘이 성장 크기에 따라 어떻게 확장되는지를 보여주는 데 사용되는 특수 표기법입니다. 성장은 준선형, 선형, 초선형 등이 될 수 있습니다. 목록 크기에 따라 실행 시간이 어떻게 증가하는지 알아야 합니다. 증가합니다. 최악의 시나리오를 설정합니다. Big O 표기법을 사용하면 작업 수를 비교할 수 있습니다. 예를 들어 이진 검색은 lg n 연산이 필요합니다.
크기 n의 목록을 확인합니다. Big O 표기법의 실행 시간은 O(log n)입니다.

가장 빠른 것부터 가장 느린 것 순으로 정렬된 일반적인 Big O 실행 시간:

O(log n) - 로그 시간으로 알려져 있습니다. 예 : 이진 검색

O(n) - 선형 시간으로 알려져 있습니다. 예 : 단순 검색

O(n * log n): 퀵 정렬과 같은 빠른 정렬 알고리즘

O(n2) : 선택 정렬과 같은 느린 정렬 알고리즘입니다.

O(n!) : 순회 판매원처럼 정말 느린 알고리즘입니다.

결론
알고리즘의 속도는 초 단위가 아니라 작업 수의 증가로 측정됩니다. 대신 입력 크기가 증가함에 따라 알고리즘의 튜닝 시간이 얼마나 빨리 증가하는지에 대해 이야기합니다. 다음 기사에서는 다양한 Big O 실행 시간에 대해 다룰 것입니다.