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

def quick_sort(arr):
    """Быстрая сортировка списка."""
    # Базовый случай: массив из 0 или 1 элемента уже отсортирован
    if len(arr) <= 1:
        return arr
    else:
        # Выбираем опорный элемент (средний по индексу)
        pivot = arr[len(arr) // 2]
        
        # Создаём три подмассива:
        # left - все элементы меньше опорного
        left = [x for x in arr if x < pivot]
        
        # middle - все элементы равные опорному
        middle = [x for x in arr if x == pivot]
        
        # right - все элементы больше опорного
        right = [x for x in arr if x > pivot]
        
        # Рекурсивно сортируем левую и правую части,
        # объединяем результаты
        return quick_sort(left) + middle + quick_sort(right)

Наличие группы middle в реализации принципиально важно для корректной обработки массивов с повторяющимися элементами. Без неё алгоритм может попасть в бесконечную рекурсию, пытаясь сортировать одинаковые значения.

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

import random
pivot = arr[random.randint(0, len(arr)-1)]

Пространственная сложность представленной реализации составляет O(n), так как на каждом уровне рекурсии создаются новые списки. Однако существует оптимизированная версия алгоритма, выполняющая сортировку на месте, которая требует O(log n) дополнительной памяти для стека рекурсии.

Сравнение быстрой сортировки с сортировкой слиянием выявляет их ключевые различия. Оба алгоритма имеют среднюю сложность O(n log n), но сортировка слиянием гарантирует эту сложность даже в худшем случае, тогда как быстрая сортировка может деградировать до O(n²). С другой стороны, быстрая сортировка часто оказывается быстрее на практике из-за меньших константных множителей и может быть реализована с меньшим потреблением памяти. Сортировка слиянием является стабильной — она сохраняет относительный порядок равных элементов, что не всегда верно для классической in-place реализации быстрой сортировки.

Встроенная функция sort() в Python использует более сложный гибридный алгоритм — Timsort. Он сочетает в себе идеи сортировки слиянием и сортировки вставками. Timsort эффективно использует уже существующие упорядоченные подпоследовательности в данных, что делает его особенно быстрым для частично отсортированных массивов, где он может достигать сложности O(n). Этот алгоритм является стабильным и гарантирует производительность O(n log n) в худшем случае, что делает его отличным выбором для стандартной библиотеки Python. Пример его использования:

data = [64, 34, 25, 12, 22, 11, 90]
data.sort()
sorted_data = sorted(data, reverse=True)

Таким образом, быстрая сортировка остается важным и фундаментальным алгоритмом, наглядно демонстрирующим принцип «разделяй и властвуй». Она эффективна на практике, хотя и требует внимательного подхода к выбору опорного элемента. Для большинства повседневных задач предпочтительнее использовать оптимизированные встроенные средства языка, такие как Timsort в Python, но глубокое понимание работы быстрой сортировки необходимо для анализа алгоритмов и решения специализированных задач.

#algorithm

Подводя итог, можно выделить ключевые характеристики бинарного поиска. Во-первых, он применим исключительно к отсортированным массивам. Во-вторых, его временная сложность O(log n) делает его чрезвычайно быстрым для больших наборов данных. В-третьих, принцип работы основан на постоянном уменьшении области поиска вдвое. Наконец, алгоритм возвращает индекс найденного элемента или специальное значение (например, -1), если элемент отсутствует. По сравнению с линейным поиском бинарный поиск демонстрирует подавляющее преимущество в скорости на крупных массивах, что делает его одним из фундаментальных алгоритмов в информатике.

#algorithm

def delete_by_value(self, data):
    # Случай 1: Список пустой
    if not self.head:
        return
    
    # Случай 2: Удаляем голову
    if self.head.data == data:
        self.head = self.head.next  # Просто сдвигаем голову
        return
    
    # Случай 3: Удаляем элемент из середины/конца
    current_node = self.head
    
    # Ищем узел ПЕРЕД тем, который нужно удалить
    while current_node.next:
        if current_node.next.data == data:
            # "Перепрыгиваем" через удаляемый узел
            current_node.next = current_node.next.next
            return
        current_node = current_node.next

Наглядно этот процесс выглядит так:

Исходный список:
head → [10|•]→[20|•]→[30|•]→[40|×]

Удаляем 20:

Шаг 1: Находим узел ПЕРЕД удаляемым
head → [10|•]→[20|•]→[30|•]→[40|×]
       ↑       ↑
    current  current.next (удаляем это)

Шаг 2: "Перепрыгиваем" через 20
current.next = current.next.next

head → [10|•]─────→[30|•]→[40|×]
             \    /
              [20|•] (потерян, будет удален сборщиком мусора)

Пример использования:

ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.append(40)

print(ll.display())  # [10, 20, 30, 40]

ll.delete_by_value(20)
print(ll.display())  # [10, 30, 40]

ll.delete_by_value(10)  # Удаляем голову
print(ll.display())  # [30, 40]

Более сложной и гибкой вариацией является двусвязный список. В нем каждый узел содержит уже две ссылки: не только на следующий, но и на предыдущий узел. Это позволяет обходить список в обоих направлениях.

class DoubleNode:
    def __init__(self, data):
        self.data = data
        self.next = None  # Ссылка вперед
        self.prev = None  # Ссылка назад

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

Двусвязный список:
None ← head                    tail → None
       [×|10|•]↔️[•|20|•]↔️[•|30|×]
        ↑    ↑    ↑    ↑    ↑    ↑
       prev next prev next prev next

Реализация двусвязного списка включает поддержку ссылки не только на голову, но и на хвост.

Пример 2

Пример показывает его новые возможности:

dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)

print(dll.display_forward())   # [10, 20, 30]
print(dll.display_backward())  # [30, 20, 10]

Преимущества двусвязного списка включают возможность двустороннего обхода, более простое удаление узла, так как ссылка на предыдущий элемент уже известна, и добавление в конец за O(1) благодаря наличию ссылки на хвост. Однако за эти удобства приходится платить дополнительной памятью на хранение второй ссылки в каждом узле и усложнением логики управления связями.

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

#algorithm