Algoritmy vyhledávání O(log n) vs O(n) v Pythonu

Porovnání vyhledávacích algoritmů: od O(n) po O(log n) pro vývojáře

U polí s miliony prvků vyžaduje lineární vyhledávání až 10 milionů operací, zatímco binární vyhledávání se vejde do 24 porovnání. Podrobný rozbor čtyř vyhledávacích algoritmů v Pythonu s analýzou časové složitosti a praktickými doporučeními pro výběr. Zahrnuje ochranu proti přetečení, funkce lower_bound/upper_bound a příklady z LeetCode.

Úkol vyhledávání: v kolekci arr najít index hodnoty target nebo vrátit -1. Kolekce může být setříděná či nesetříděná, statická nebo dynamická. Typické použití: vyhledávání SKU v e-commerce (miliony položek), ověřování ID transakcí ve fintech.

Lineární vyhledávání pro nesetříděná data

Vhodné pro jakoukoli kolekci. Postupně prochází všechny prvky.

Implementace:

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Složitost:

• Čas: O(n) v nejhorším a průměrném případě, O(1) v nejlepším.
• Paměť: O(1).

Binární vyhledávání a jeho varianty

Vyžaduje setříděné pole. Interval opakovaně dělí napůl.

Iterativní implementace: použijte mid = left + (right - left) // 2, abyste zabránili přetečení (důležité v C++/Java; v Pythonu je bezpečné).

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

def upper_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

# Příklad
sorted_arr = [1, 3, 3, 5, 7, 9]
print(binary_search(sorted_arr, 5))  # 3
print(lower_bound(sorted_arr, 3))     # 1
print(upper_bound(sorted_arr, 3))     # 3

Složitost: O(log n) čas, O(1) paměť.

Funkce lower_bound vrací pozici pro vložení zleva, upper_bound zprava od target. Užitečné při práci s duplikáty a úlohách na LeetCode.

Exponenciální vyhledávání pro streamová data

Pro setříděná pole neznámé délky nebo když je target blízko začátku. Nejprve exponenciálně rozšiřuje hranice intervalu, poté aplikuje binární vyhledávání.

def exponential_search(arr, target):
    if not arr:
        return -1
    if arr[0] == target:
        return 0

    bound = 1
    while bound < len(arr) and arr[bound] < target:
        bound *= 2

    left = bound // 2
    right = min(bound, len(arr) - 1)
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Příklad
big_arr = list(range(1_000_000))
print(exponential_search(big_arr, 123456))  # 123456

Složitost: O(log i), kde i je pozice prvku; v nejhorším případě O(log n), paměť O(1).

Hashovací vyhledávání pro dynamické kolekce

Průměrná složitost O(1) díky hashovacím tabulkám (set/dict v Pythonu).

def hash_search_set(arr, target):
    s = set(arr)
    return target in s

def hash_search_dict(pairs, key):
    d = dict(pairs)
    return d.get(key)

# Příklad
nums = [10, 20, 30, 40]
print(hash_search_set(nums, 30))  # True
pairs = [("a", 1), ("b", 2)]
print(hash_search_dict(pairs, "b"))  # 2

Složitost: O(1) průměrně, O(n) v nejhorším případě (kolize), paměť O(n).

Doporučení pro výběr algoritmu

• Nesetříděné pole: lineární vyhledávání pro N < 100 nebo vzácné dotazy.
• Setříděné statické pole: binární vyhledávání.
• Dynamické pole s vkládáním: hashovací tabulka (pokud není důležité pořadí prvků).
• Streamová data/neznámá velikost: exponenciální vyhledávání.

| Algoritmus | Průměrný čas | Nejhorší čas | Paměť | Požadavky |

|------------|--------------|--------------|--------|-----------|

| Lineární | O(n) | O(n) | O(1) | Jakákoli kolekce |

| Binární | O(log n) | O(log n) | O(1) | Setříděné pole |

| Exponenciální | O(log i) | O(log n) | O(1) | Setříděné pole |

| Hash | O(1) | O(n) | O(n) | Hashovatelné klíče |

Klíčové body

• Pro 10 milionů prvků vyžaduje binární vyhledávání pouze 24 operací oproti 10 milionům u lineárního.
• V binárním vyhledávání vždy používejte bezpečný výpočet mid.
• Hashovací tabulky spotřebují O(n) paměti, ale poskytují průměrný čas O(1).
• Funkce lower_bound a upper_bound jsou nezbytné pro práci s duplikáty a určování pozic vkládání.
• Exponenciální vyhledávání je ideální pro prvky nacházející se blízko začátku velkých polí.

— Editorial Team