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

Поиск среди 16 отсортированных элементов займет не более 4 шагов.

Помимо временной, важна и пространственная сложность, которая оценивает объем дополнительной памяти, требуемой алгоритмом. Например, алгоритм нахождения максимума в массиве использует фиксированный объем памяти O(1), тогда как создание полной копии списка потребует памяти O(n).

Практическое значение асимптотического анализа становится очевидным при сравнении алгоритмов. Рассмотрим задачу поиска дубликатов. Наивный подход с двойным циклом имеет сложность O(n²):

def find_duplicates_slow(arr):
    duplicates = []
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j] and arr[i] not in duplicates:
                duplicates.append(arr[i])
    return duplicates

Более разумный подход с использованием хэш-множества имеет сложность O(n):

def find_duplicates_fast(arr):
    seen = set()
    duplicates = set()
    for item in arr:
        if item in seen:
            duplicates.add(item)
        else:
            seen.add(item)
    return list(duplicates)

На списке из тысячи элементов второй алгоритм окажется в сотни раз быстрее первого.

Для наглядности можно представить себе сводную таблицу сложностей. O(1) обозначает мгновенное выполнение, например доступ к элементу массива по индексу. O(log n) характерна для алгоритмов типа бинарного поиска. O(n) — для линейного прохода по данным. O(n log n) — это типичная сложность эффективных алгоритмов сортировки. O(n²) часто возникает при обработке матриц или использовании вложенных циклов. O(2ⁿ) — экстремально медленная сложность, присущая некоторым задачам полного перебора.

Понимание этих принципов позволяет делать осознанный выбор алгоритма, что является фундаментальным навыком в разработке эффективных программ.

#algorithm