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

Тем не менее, рекурсия остаётся незаменимым инструментом для задач, имеющих естественную рекурсивную структуру данных или логики. Она идеально подходит для обхода древовидных структур (каталогов файловой системы), реализации алгоритмов "разделяй и властвуй" (быстрая сортировка, бинарный поиск) и решения таких задач, как Ханойские башни. Выбор между рекурсией и итерацией часто является компромиссом между читаемостью, простотой выражения идеи алгоритма и требованиями к производительности и ресурсам.

#algorithm

Интересной задачей является реализация очереди с помощью двух стеков. Классическое решение использует один стек для добавления элементов (enqueue), а другой — для удаления (dequeue). Когда требуется удалить элемент, но второй стек пуст, все элементы перекладываются из первого стека во второй, в результате чего порядок инвертируется и первый добавленный элемент оказывается на вершине второго стека, готовый к извлечению.

Пример 8

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

Помимо уже упомянутых случаев, стек используется во многих других областях. История браузера — это классический пример, где посещенные страницы складываются в стек для кнопки «Назад».

Пример 9

Функция отмены действий в редакторах также полагается на стек для хранения состояний.

Пример 10

Стек вызовов, управляющий выполнением функций в программе, — еще один яркий пример. Когда функция вызывает другую, ее контекст помещается в стек, а после завершения вложенной функции — восстанавливается.

Пример 11

Проверка корректности HTML-тегов — задача, где стек отслеживает вложенность открывающих и закрывающих элементов.

Пример 12

Для реализации очереди в Python оптимально использовать класс deque из модуля collections. Это двусторонняя очередь, которая обеспечивает константную сложность O(1) для операций добавления и удаления с обоих концов, в отличие от списка, где удаление из начала (pop(0)) имеет линейную сложность O(n). Полноценная реализация очереди на deque включает все основные операции.

Пример 13

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

Пример 14

С точки зрения сложности операций, стек на основе списка Python обеспечивает O(1) для push, pop и peek, так же как и проверка на пустоту. Очередь на основе deque также гарантирует O(1) для enqueue, dequeue, front и isEmpty. Важно подчеркнуть, что использование обычного списка для очереди неэффективно из-за линейной сложности операции pop(0), что делает deque предпочтительным выбором.

В заключение, стек и очередь — это фундаментальные структуры данных, каждая со своим строгим принципом доступа: LIFO для стека, подобно стопке тарелок, и FIFO для очереди, как очередь людей. Их понимание критически важно для изучения алгоритмов и системного программирования, поскольку они лежат в основе множества механизмов — от управления памятью и планирования процессов до синтаксического анализа и работы с историей. Ключевые моменты для запоминания: стек оперирует с одним концом, очередь — с двумя; в Python для стека используется list, для очереди — deque; обе структуры обеспечивают высокую эффективность основных операций.

#algorithm

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

# Пример 1: Обычная сортировка
data1 = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(data1.copy()))
# Результат: [11, 12, 22, 25, 34, 64, 90]

# Пример 2: Уже отсортированный список
data2 = [1, 2, 3, 4, 5]
print(bubble_sort(data2.copy()))
# Результат: [1, 2, 3, 4, 5]

# Пример 3: Обратный порядок
data3 = [5, 4, 3, 2, 1]
print(bubble_sort(data3.copy()))
# Результат: [1, 2, 3, 4, 5]

Чтобы лучше проследить за ходом алгоритма, можно использовать визуализированную версию:

def bubble_sort_visualized(arr):
    n = len(arr)
    print(f"Начальный список: {arr}")
    print()
    
    for i in range(n):
        print(f"=== Проход {i + 1} ===")
        swapped = False
        
        for j in range(0, n - i - 1):
            print(f"Сравниваем {arr[j]} и {arr[j + 1]}", end=" ")
            
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
                print(f"→ Меняем! Теперь: {arr}")
            else:
                print(f"→ Оставляем")
        
        if not swapped:
            print("Обменов не было, список отсортирован!")
            break
        print()
    
    print(f"\nИтоговый список: {arr}")
    return arr

data = [5, 2, 8, 1, 9]
bubble_sort_visualized(data)

Одним из недостатков пузырьковой сортировки является её низкая эффективность на больших наборах данных. Сложность алгоритма в худшем и среднем случае оценивается как O(n²), где n — количество элементов. Это означает, что с ростом размера списка количество необходимых операций сравнения и обмена растёт квадратично. Например, для тысячи элементов может потребоваться около миллиона сравнений, в то время как более совершенные алгоритмы, такие как быстрая сортировка, справляются с этой задачей за порядка двадцати тысяч операций. Именно поэтому пузырьковая сортировка, при всей своей простоте и наглядности, не применяется в реальных проектах с большими объёмами данных.

Алгоритм можно модифицировать для сортировки по убыванию. Для этого достаточно изменить условие сравнения с > на <, чтобы более мелкие элементы перемещались вправо:

def bubble_sort_descending(arr):
    """Пузырьковая сортировка в порядке УБЫВАНИЯ."""
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] < arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

data1 = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort_descending(data1.copy()))
# Результат: [90, 64, 34, 25, 22, 12, 11]

Также можно создать универсальную функцию, принимающую параметр reverse для выбора направления сортировки.

В заключение, пузырьковая сортировка служит отличным учебным инструментом для понимания базовых принципов алгоритмов сортировки. Она проста для восприятия и реализации, корректно работает на любых данных, но из-за квадратичной сложности неприменима для серьёзных задач. Её изучение даёт необходимую основу для перехода к более эффективным алгоритмам.

#algorithm