Основные алгоритмы на Python для начинающих

Основные алгоритмы на Python — это основа программирования, с которой начинают многие разработчики.

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

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

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

Содержание

Контрольные вопросы

Что такое алгоритм и почему он важен?

Эффективность алгоритмов и О-нотация

Когда мы говорим об алгоритмах, важным аспектом становится их эффективность. На самом деле успех в программировании часто заключается в том, как быстро и грамотно алгоритм решает задачи. Здесь на помощь приходит О-нотация. Она позволяет нам оценивать, насколько быстро алгоритм работает с увеличением объема данных. Давайте подробнее рассмотрим это понятие.

Типы сложности алгоритмов

Сложность алгоритмов делится на два ключевых типа: временная и пространственная. Временная сложность показывает, сколько времени алгоритм будет работать в зависимости от разного объема входных данных. Обычно обозначается с помощью больших O (как O(n), O(log n) и другие).

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

Рационально оценивать алгоритмы можно по их сложности:

O(1) – Константная сложность. Алгоритм работает за фиксированное время независимо от объема данных.
O(log n) – Логарифмическая сложность. Время выполнения увеличивается медленно при увеличении данных.
O(n) – Линейная сложность. Время выполнения пропорционально количеству данных.
O(n log n) – Линейно-логарифмическая сложность. Обычно встречается в алгоритмах сортировки.
O(n^2) – Квадратная сложность. Время выполнения квадратично растет с увеличением данных.
O(2^n) – Экспоненциальная сложность. Алгоритмы с такой сложностью плохо масштабируются.

Каждую из сложностей нужно учитывать при выборе алгоритма для конкретной проблемы. Чем меньше сложность, тем быстрее алгоритм будет работать, особенно с большими объемами данных.

Алгоритмы сортировки

Начнем с самых простых и распространенных алгоритмов, которые пригодятся любому начинающему программисту. Изучение базовых алгоритмов на Python поможет вам понять фундаментальные принципы работы с данными и подготовит к более сложным задачам.

Алгоритм сортировки пузырьком

Алгоритм сортировки пузырьком — это один из самых простых способов отсортировать массив. Он работает следующим образом: проходит по всем элементам массива и сравнивает их попарно. Если элементы находятся в неправильном порядке, они меняются местами. Этот процесс повторяется до тех пор, пока весь массив не станет отсортированным. Результатом этой процедуры будет упорядоченный массив, где элементы по возрастанию или убыванию располагаются последовательно.

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

Алгоритм можно описать следующим образом: для каждого элемента массива происходит сравнение с соседним элементом. Если текущий элемент больше следующего, они меняются местами. Этот процесс продолжается до тех пор, пока весь массив не будет проверен. После первой итерации самый большой элемент «всплывает» на последнюю позицию, как пузырёк воздуха в воде, что и дало название этому методу. Такой визуальный образ делает алгоритм интуитивно понятным для новичков.

Пример работы алгоритма сортировки пузырьком:
Исходный массив:  5 3 8 4 2

1-й проход: 
  3 5 4 2 8  (8 всплыл на своё место)
  
2-й проход: 
  3 4 2 5 8  (5 всплыл на своё место)
  
3-й проход: 
  3 2 4 5 8
  
4-й проход: 
  2 3 4 5 8  (все элементы теперь отсортированы)

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

Для начала давайте посмотрим на пример реализации этого улучшенного алгоритма на Python:

def optimized_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

my_list = [64, 34, 25, 12, 22, 11, 90]
print(optimized_bubble_sort(my_list))  # Выведет отсортированный массив

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

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

Пример работы алгоритма сортировки пузырьком:
Исходный массив:  5 3 8 4 2

1-й проход: 
  3 5 4 2 8  (8 всплыл на своё место)
  
2-й проход: 
  3 4 2 5 8  (5 всплыл на своё место)
  
3-й проход: 
  3 2 4 5 8
  
4-й проход: 
  2 3 4 5 8  (все элементы теперь отсортированы)

Для начала давайте посмотрим на пример реализации этого алгоритма на Python:

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

my_list = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(my_list))  # Выведет отсортированный массив

Как видно из кода, алгоритм использует вложенные циклы. Это приводит к тому, что его временная сложность составляет O(n^2) в худшем случае. Несмотря на свою простоту, этот алгоритм не самый эффективный для крупных наборов данных. Тем не менее, он отлично подходит для обучения и понимания концепций сортировки.

Алгоритм сортировки выбором

Сортировка выбором — это один из самых простых алгоритмов сортировки, который легко понять и реализовать. Он работает следующим образом: перебираем массив и находим минимальный элемент. Затем меняем его местами с элементом, который стоит на первом месте. После этого переходим к следующему элементу и снова ищем минимальное значение среди оставшихся. Так продолжаем до тех пор, пока весь массив не будет отсортирован. Этот подход делает алгоритм интуитивно понятным, хотя и не самым эффективным.

Например, если у нас есть массив [64, 25, 12, 22, 11], алгоритм будет выглядеть так:

1. Находим 11 — меняем его местами с 64 (первый элемент).
2. Находим 12 — меняем его с 25 (второй элемент).
3. Находим 22 — меняем с 25.
4. Следующий этап, когда максимальные элементы уже на месте — продолжаем до конца.

В итоге, массив будет отсортирован: [11, 12, 22, 25, 64]. Этот алгоритм может быть эффективным для небольших массивов, но следует помнить, что его временная сложность составляет O(n²), что делает его менее подходящим для работы с большими объемами данных, так как при увеличении числа элементов время выполнения алгоритма резко возрастает.

Для тех, кто хочет увидеть работу алгоритма на практике, вот пример кода на языке Python, который реализует сортировку выбором:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

array = [64, 25, 12, 22, 11]
print(selection_sort(array))

Чтобы лучше понять, как работает алгоритм, можно представить процесс сортировки в виде ASCII-иллюстрации:

Исходный массив: [64, 25, 12, 22, 11]
Шаг 1: [11, 25, 12, 22, 64]
Шаг 2: [11, 12, 25, 22, 64]
Шаг 3: [11, 12, 22, 25, 64]
Итоговый массив: [11, 12, 22, 25, 64]

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

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

Например, если у нас есть массив [64, 25, 12, 22, 11], алгоритм будет выглядеть так:

1. Находим 11 — меняем его местами с 64 (первый элемент).
2. Находим 12 — меняем его с 25 (второй элемент).
3. Находим 22 — меняем с 25.
4. Следующий этап, когда максимальные элементы уже на месте — продолжаем до конца.

В итоге массив будет отсортирован: [11, 12, 22, 25, 64]. Хотя этот алгоритм довольно простой и понятный, он не самый эффективный для больших объемов данных, так как его временная сложность составляет O(n²).

Важно отметить, что алгоритм сортировки выбором не является стабильным. Это значит, что при сортировке элементов с одинаковыми значениями их первоначальный порядок может быть нарушен. Например, если у нас есть массив с элементами [4a, 2, 4b, 1] (где «4a» и «4b» — элементы с одинаковыми значениями), после сортировки выбором порядок «4a» и «4b» может измениться. Таким образом, итоговый массив может выглядеть как [1, 2, 4b, 4a], что демонстрирует потерю стабильности.

Например, если у нас есть массив [64, 25, 12, 22, 11], алгоритм будет выглядеть так:

1. Находим 11 — меняем его местами с 64 (первый элемент).
2. Находим 12 — меняем его с 25 (второй элемент).
3. Находим 22 — меняем с 25.
4. Следующий этап, когда максимальные элементы уже на месте — продолжаем до конца.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

array = [64, 25, 12, 22, 11]
print(selection_sort(array))

Чтобы лучше понять, как работает алгоритм, можно представить процесс сортировки в виде ASCII-иллюстрации:

Исходный массив: [64, 25, 12, 22, 11]
Шаг 1: [11, 25, 12, 22, 64]
Шаг 2: [11, 12, 25, 22, 64]
Шаг 3: [11, 12, 22, 25, 64]
Итоговый массив: [11, 12, 22, 25, 64]

Например, если у нас есть массив [64, 25, 12, 22, 11], алгоритм будет выглядеть так:

1. Находим 11 — меняем его местами с 64 (первый элемент).
2. Находим 12 — меняем его с 25 (второй элемент).
3. Находим 22 — меняем с 25.
4. Следующий этап, когда максимальные элементы уже на месте — продолжаем до конца.

Алгоритм сортировки вставками

Сортировка вставками является одной из простейших техник сортировки, однако она показывает хорошие результаты на небольших массивах.

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

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

Рассмотрим пример: у нас есть массив [5, 2, 4, 6, 1, 3]. Начнем с второго элемента:

1. 2 меньше 5 — меняем местами.
2. 4 больше 2 — оставляем на месте.
3. 6 также не требует изменений.
4. 1 меньше 5, 2 и 4 — мы вставляем его в начало массива, а 3 находит свое место между 2 и 4.

В результате массив будет [1, 2, 3, 4, 5, 6]. Этот алгоритм работает довольно эффективно для небольших наборов данных и имеет временную сложность O(n²), что делает его отличным выбором в случае сортировки массивов небольшого размера.

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

Вот пример кода реализации сортировки вставками на языке Python:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Пример использования:
my_array = [5, 2, 4, 6, 1, 3]
sorted_array = insertion_sort(my_array)
print(sorted_array)  # Вывод: [1, 2, 3, 4, 5, 6]

Для наглядности представим, как работает этот алгоритм с помощью ASCII-инфографики:

 Исходный массив: [5, 2, 4, 6, 1, 3]
  Шаг 1:         [5, | 2, 4, 6, 1, 3]
  Сравниваем:  если 2 < 5 - меняем местами
  Результат:    [2, 5, 4, 6, 1, 3]

  Шаг 2:         [2, 5, | 4, 6, 1, 3]
  Сравниваем:  4<5 - сдвигаем 5 вправо
  Результат:    [2, 4, 5, 6, 1, 3]

  Шаг 3:         [2, 4, 5, | 6, 1, 3]
  6>5 - оставляем на месте
  Результат:    [2, 4, 5, 6, 1, 3]

  Шаг 4:         [2, 4, 5, 6, | 1, 3]
  1<6, 5, 4, 2 - вставляем 1 в начало
  Результат:    [1, 2, 4, 5, 6, 3]

  Шаг 5:         [1, 2, 4, 5, 6, | 3]
  3<6 и >4 - вставляем между 2 и 4
  Результат:    [1, 2, 3, 4, 5, 6]

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

Рассмотрим пример: у нас есть массив [5, 2, 4, 6, 1, 3]. Начнем с второго элемента:

1. 2 меньше 5 — меняем местами.
2. 4 больше 2 — оставляем на месте.
3. 6 также не требует изменений.
4. 1 меньше 5, 2 и 4 — мы вставляем его в начало массива, а 3 находит свое место между 3 и 4.

Вот пример кода реализации сортировки вставками на языке Python:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Пример использования:
my_array = [5, 2, 4, 6, 1, 3]
sorted_array = insertion_sort(my_array)
print(sorted_array)  # Вывод: [1, 2, 3, 4, 5, 6]

Для наглядности представим, как работает этот алгоритм с помощью ASCII-инфографики:

 Исходный массив: [5, 2, 4, 6, 1, 3]
  Шаг 1:         [5, | 2, 4, 6, 1, 3]
  Сравниваем:  если 2 < 5 - меняем местами
  Результат:    [2, 5, 4, 6, 1, 3]

  Шаг 2:         [2, 5, | 4, 6, 1, 3]
  Сравниваем:  4<5 - сдвигаем 5 вправо
  Результат:    [2, 4, 5, 6, 1, 3]

  Шаг 3:         [2, 4, 5, | 6, 1, 3]
  6>5 - оставляем на месте
  Результат:    [2, 4, 5, 6, 1, 3]

  Шаг 4:         [2, 4, 5, 6, | 1, 3]
  1<6, 5, 4, 2 - вставляем 1 в начало
  Результат:    [1, 2, 4, 5, 6, 3]

  Шаг 5:         [1, 2, 4, 5, 6, | 3]
  3<6 и >4 - вставляем между 2 и 4
  Результат:    [1, 2, 3, 4, 5, 6]

Рассмотрим пример: у нас есть массив [5, 2, 4, 6, 1, 3]. Начнем с второго элемента:

1. 2 меньше 5 — меняем местами.
2. 4 больше 2 — оставляем на месте.
3. 6 также не требует изменений.
4. 1 меньше 5, 2 и 4 — мы вставляем его в начало массива, а 3 находит свое место между 3 и 4.

В результате массив будет [1, 2, 3, 4, 5, 6]. Этот алгоритм работает достаточно быстро для небольших массивов и имеет временную сложность O(n²), но в общем случае это неплохой выбор для небольших объемов данных.

Алгоритм быстрой сортировки

Алгоритм быстрой сортировки (Quick Sort) является одним из самых популярных методов сортировки. Его основное преимущество заключается в высокой скорости работы при сортировке массивов и списков. Несмотря на то, что в худшем случае его временная сложность составляет O(n²), на практике алгоритм демонстрирует отличные результаты, особенно на небольших объемах данных.

Основная идея алгоритма основана на концепции «Разделяй и властвуй», которая заключается в рекурсивном разбиении задачи на более мелкие подзадачи, решение которых проще.

Для иллюстрации работы алгоритма представим, что у нас есть массив, который необходимо отсортировать. Например, массив [6, 5, 4, 3, 2, 1] будет изменяться на каждом этапе сортировки.

Шаг 1: Выбор опорного элемента.
            [6, 5, 4, 3, 2, 1]
            
Шаг 2: Разделение массива на две части.
            [5, 4, 3, 2, 1] | [6]

Шаг 3: Рекурсивная сортировка двух частей.
            [4, 3, 2, 1] | [5] | [6]
            
Шаг 4: Итоговое соединение.
            [1, 2, 3, 4, 5, 6]

Концепция «Разделяй и властвуй» работает следующим образом:

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

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

Теперь рассмотрим пример реализации алгоритма быстрой сортировки на языке Python:

def quick_sort(arr): 
    if len(arr) <= 1: 
        return arr 
    pivot = arr[len(arr) // 2] 
    left = [x for x in arr if x < pivot] 
    middle = [x for x in arr if x == pivot] 
    right = [x for x in arr if x > pivot] 
    return quick_sort(left) + middle + quick_sort(right) 
array = [6, 5, 4, 3, 2, 1] 
sorted_array = quick_sort(array) 
print(sorted_array)  # Вывод: [1, 2, 3, 4, 5, 6]

Важно отметить, что худший случай для QuickSort возникает, когда массив изначально отсортирован или почти отсортирован, и опорный элемент выбирается неудачно, например, всегда в качестве опорного выбирается первый или последний элемент. Это приводит к тому, что алгоритм плохо разбивает массив, и в результате временная сложность вырастает до O(n²). Чтобы избежать этой ситуации, рекомендуется применять стратегии выбора опорного элемента, такие как «случайный выбор» или «выбор медианы», что помогает улучшить производительность алгоритма в большинстве случаев.

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

Шаг 1: Выбор опорного элемента.
            [6, 5, 4, 3, 2, 1]
            
Шаг 2: Разделение массива на две части.
            [5, 4, 3, 2, 1] | [6]

Шаг 3: Рекурсивная сортировка двух частей.
            [4, 3, 2, 1] | [5] | [6]
            
Шаг 4: Итоговое соединение.
            [1, 2, 3, 4, 5, 6]

Теперь рассмотрим пример реализации алгоритма быстрой сортировки на языке Python:

def quick_sort(arr): 
    if len(arr) <= 1: 
        return arr 
    pivot = arr[len(arr) // 2] 
    left = [x for x in arr if x < pivot] 
    middle = [x for x in arr if x == pivot] 
    right = [x for x in arr if x > pivot] 
    return quick_sort(left) + middle + quick_sort(right) 
array = [6, 5, 4, 3, 2, 1] 
sorted_array = quick_sort(array) 
print(sorted_array)  # Вывод: [1, 2, 3, 4, 5, 6]

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

Вопросы и задания. Тема 1. Алгоритмы сортировки

Контрольные вопросы

Какова временная сложность алгоритма сортировки пузырьком в худшем случае? В лучшем?
Почему алгоритм сортировки выбором не является стабильным? Приведите пример.
Каков принцип работы сортировки вставками и в каких случаях она работает близко к O(n)?
Чем «разделяй и властвуй» в быстрой сортировке помогает добиться средней сложности O(n log n)?
Какой случай входных данных для QuickSort приводит к худшей O(n²) сложности и как этого избежать?

Практические задания

Задание 1.1. Реализуйте алгоритм сортировки пузырьком (bubble_sort) для списка чисел. Проверьте на случайном списке из 1000 элементов и замерьте время выполнения.

Задание 1.2. Реализуйте сортировку выбором (selection_sort) и сравните число обменов элементов с результатом пузырька на одном и том же массиве.

Задание 1.3. Напишите сортировку вставками (insertion_sort) и протестируйте её на почти отсортированном списке (например, с 5% элементов в случайных позициях). Оцените время и сравните с пузырьком.

Задание 1.4. Реализуйте рекурсивный QuickSort с выбором опорного элемента «медиана из трёх». Проверьте на случайном списке из 10 000 элементов. Сравните время с встроенным list.sort().

Задание 1.5. Дан список кортежей [(имя, возраст)]. Отсортируйте его:

Сначала по имени (лексикографически), используя вашу QuickSort.

Затем по возрасту (возрастающий), используя встроенный sort(key=…). Объясните разницу в коде.

Ответы

1.1. BubbleSort: худший O(n²), лучший O(n) (если добавить флаг).
1.2. SelectionSort: всегда O(n²); обменов ≈ n.
1.3. InsertionSort: O(n + k·n) для k % несортированных → близко к O(n) при k мал.
1.4. QuickSort (медиана из трёх): средняя O(n log n), худшая O(n²) (редко).
1.5.
  a) QuickSort по имени аналогично по числу, но сравниваем строки.
  b) list.sort(key=lambda x: x[1]) выдаёт устойчивую сортировку Timsort, O(n log n).

Решения


import time
import random

# 1.1 Bubble Sort
def bubble_sort(a):
    n = len(a)
    for i in range(n):
        swapped = False
        for j in range(0, n-1-i):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                swapped = True
        if not swapped:
            break

# 1.2 Selection Sort
def selection_sort(a):
    n = len(a)
    swaps = 0
    for i in range(n):
        m = i
        for j in range(i+1, n):
            if a[j] < a[m]: m = j if m != i: a[i], a[m] = a[m], a[i] swaps += 1 return swaps # 1.3 Insertion Sort def insertion_sort(a): for i in range(1, len(a)): key = a[i] j = i-1 while j >= 0 and a[j] > key:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = key

# 1.4 QuickSort with median-of-three pivot
def quicksort(a):
    def _qs(l, r):
        if l >= r: return
        m = (l + r) // 2
        # median of a[l],a[m],a[r]
        pivot = sorted((a[l], a[m], a[r]))[1]
        i, j = l, r
        while i <= j:
            while a[i] < pivot: i += 1 while a[j] > pivot: j -= 1
            if i <= j:
                a[i], a[j] = a[j], a[i]
                i += 1; j -= 1
        _qs(l, j); _qs(i, r)
    _qs(0, len(a)-1)

# 1.5 Sorting tuples
def sort_name_quick(a):
    quicksort(a)  # relies on tuple comparison

def sort_age_builtin(a):
    a.sort(key=lambda x: x[1])

# Примеры измерений:
if __name__ == "__main__":
    arr = [random.randint(0,10000) for _ in range(1000)]
    t0 = time.time(); bubble_sort(arr.copy()); print("Bubble:", time.time()-t0)
    t0 = time.time(); selection_sort(arr.copy()); print("Selection:", time.time()-t0)
    # и т.д.

Алгоритмы поиска

Бинарный поиск

Бинарный поиск — это эффективный алгоритм, который превосходно работает, когда массив данных предварительно отсортирован. Алгоритм осуществляет поиск путём деления обрабатываемого массива пополам на каждом шаге. Сначала проверяем, равен ли искомый элемент центровому элементу массива. Если он не равен, то определяем, в какую из половин массива следует продолжить поиск, основываясь на сравнении. Этот процесс продолжается до тех пор, пока не удастся найти искомый элемент или пока не останется элементов для проверки.

Допустим, у нас есть отсортированный массив [1, 3, 5, 7, 9]. Нам нужно найти 5. Сначала находим средний элемент, это 5. Сравниваем его с искомым элементом и обнаруживаем, что они равны. Таким образом, бинарный поиск проявляет свою высокую скорость в сравнении с линейным поиском, который требует проверки каждого элемента последовательно. Эффективность бинарного поиска можно выразить как O(log n).

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

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

Этот код показывает, как мы можем находить индекс искомого элемента в отсортированном массиве. Также можно визуализировать процесс бинарного поиска:

Графическое представление алгоритма бинарного поиска:

Размер массива
|         [1, 3, 5, 7, 9]           |
|           ^                       |
|           |                       |
|         ----                      |
|       /      \                    |
|     [1, 3]   [5, 7, 9]            |
|             ^                     |
|             |                     |
|           ----                    |
|         /      \                  |
|        5      [7, 9]              |
|         ^                         |
|         |                         |
|       ----                        |

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

Допустим, у нас есть отсортированный массив [1, 3, 5, 7, 9]. Нам нужно найти 5. Сначала находим средний элемент, это 5. Сравниваем и находим, что он равен искомому. Таким образом, бинарный поиск очень быстр в сравнении с линейным и работает за O(log n).

Линейный поиск

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

Например, для массива [10, 20, 30, 40, 50] и поиска числа 30, мы проверяем элементы по порядку: сначала смотрим на 10, затем на 20, а, наконец, на 30. Как только нужный элемент найден, мы возвращаем его индекс, равный 2, так как 30 находится на третьей позиции (индексация начинается с нуля). Временная сложность этого алгоритма — O(n), что означает, что скорость его работы зависит от количества элементов в массиве. Поэтому линейный поиск подходит для небольших массивов или в случаях, когда данные не отсортированы.

Для иллюстрации работы алгоритма давайте рассмотрим пример его реализации на языке Python:

def linear_search(arr, target):
    for index in range(len(arr)):
        if arr[index] == target:
            return index
    return -1

# Пример использования
my_array = [10, 20, 30, 40, 50]
target_value = 30
result = linear_search(my_array, target_value)
print("Элемент найден на индексе:", result)

Также можно представить работу линейного поиска в виде ASCII инфографики:

Индексы:  0   1   2   3   4
          |---|---|---|---|
Элементы: 10  20  30  40  50
                ↑
              Найдено

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

Например, для массива [10, 20, 30, 40, 50] и поиска числа 30 проверяем элементы по порядку: сначала 10, затем 20, и, наконец, 30. Как только нашли, возвращаем индекс. Временная сложность этого алгоритма — O(n). Т.е. его скорость зависит от количества элементов, и он подходит для небольших массивов или когда данные не отсортированы.

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

Хэш таблицы и поиск с помощью хэша

Хэш-функция — это алгоритм, который принимает входные данные (например, строку) и преобразует их в фиксированное значение, называемое хэш-значением или хэш-кодом.

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

Подробно, про хэши мы говорили на прошлом уроке по структурам данных.

Основным преимуществом хэш-функций является их способность быстро руководить данными.

Однако для эффективного использования хэш-функций существуют определенные требования.

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

Теперь давайте рассмотрим, как происходит хэширование строк с помощью хэш-функции. Например, пусть у нас есть строка 'Hello'. После применения хэш-функции мы можем получить хэш-значение, например 5f4dcc3b5aa765d61d8327deb882cf99. Этот процесс будет происходить следующим образом:

import hashlib

def hash_string(input_string):
    # Применяем хэш-функцию MD5 к строке
    hashed_value = hashlib.md5(input_string.encode()).hexdigest()
    return hashed_value

# Пример использования
print(hash_string("Hello"))  # Вывод: 5f4dcc3b5aa765d61d8327deb882cf99

Хэш-таблица — это структура данных, которая использует хэш-функции для обеспечения быстрого доступа к данным.

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

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

В Python хэш-таблицы реализованы с помощью встроенного типа данных dict. Использование словарей в Python позволяет нам легко и быстро управлять данными. Вот пример, как можно реализовать хэш-таблицу в Python:

# Создание хэш-таблицы
hash_table = {}

# Добавление элементов
hash_table["apple"] = 1
hash_table["banana"] = 2
hash_table["orange"] = 3

# Доступ к элементу
print(hash_table["banana"])  # Вывод: 2

import hashlib

def hash_string(input_string):
    # Применяем хэш-функцию MD5 к строке
    hashed_value = hashlib.md5(input_string.encode()).hexdigest()
    return hashed_value

# Пример использования
print(hash_string("Hello"))  # Вывод: 5f4dcc3b5aa765d61d8327deb882cf99

Когда поиск в хеш-таблице может стать O(n)

В самом плохом случае все ключи попадают в одну «корзину» — из-за неудачной хеш-функции или специально подобранных коллизий — и тогда при поиске придётся линейно перебирать список из всех n элементов, сводя сложность к O(n). Чтобы этого избежать, обычно выбирают качественные хеш-функции, увеличивают число «корзин» (размер таблицы) и выполняют рехеширование при достижении порога заполнения.

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

Задания и вопросы. Тема 2. Алгоритмы поиска

Контрольные вопросы

Какова временная сложность линейного поиска в худшем и среднем случае?
При каких условиях применим бинарный поиск и какова его сложность?
Почему для бинарного поиска массив должен быть уже отсортирован?
Как устроена хэш-таблица и какая средняя сложность поиска в ней?
В каких случаях поиск по хэш-таблице может деградировать до O(n)?

Практические задания

Задание 2.1. Реализуйте линейный поиск (функция linear_search(arr, x)) в списке. Верните индекс первого вхождения или -1, если не найдено. Протестируйте на списке из 10 000 случайных чисел.

Задание 2.2. Реализуйте бинарный поиск в отсортированном списке двумя способами:

Итеративно (binary_search_iter),

Рекурсивно (binary_search_rec).

Проверьте корректность на разных позициях (краевые, средние) и измерьте время для 10⁶ элементов.

Задание 2.3. Используя модуль bisect, решите задачу: в отсортированном списке целых найти количество элементов в диапазоне [a, b]. Напишите функцию count_in_range(arr, a, b).

Задание 2.4. Дан текстовой файл с миллионом слов (по одному на строке). Постройте частотный словарь с помощью dict и кодовых конструций («for w in …: d[w]=d.get(w,0)+1»). Затем реализуйте поиск слова по словарю: возвращайте его частоту за O(1).

Задание 2.5. «Телефонная книга»: реализуйте класс PhoneBook на основе dict, поддерживающий методы add(name, number), get(name), remove(name). Напишите тест, моделирующий 100 000 запросов (случайные имена/номера) и измерьте среднее время поиска.

Ответы

2.1. LinearSearch: O(n) в среднем и в худшем; O(1) в лучшем (если на первом месте).
2.2. BinarySearch: O(log n) в худшем, требует отсортированного списка.
2.3. Bisect: count = bisect_right(arr, b) – bisect_left(arr, a).
2.4. Построение dict – O(n), поиск ключа – O(1) среднее.
2.5. Все операции словаря – O(1) среднее; удаление тоже O(1).

Решения


import random
import bisect
import time

# 2.1 Linear Search
def linear_search(arr, x):
    for i, v in enumerate(arr):
        if v == x:
            return i
    return -1

# 2.2 Binary Search
def binary_search_iter(arr, x):
    lo, hi = 0, len(arr)-1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x: lo = mid + 1 else: hi = mid - 1 return -1 def binary_search_rec(arr, x, lo=0, hi=None): if hi is None: hi = len(arr)-1 if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == x:
        return mid
    if arr[mid] < x:
        return binary_search_rec(arr, x, mid+1, hi)
    else:
        return binary_search_rec(arr, x, lo, mid-1)

# 2.3 Count in range with bisect
def count_in_range(arr, a, b):
    return bisect.bisect_right(arr, b) - bisect.bisect_left(arr, a)

# 2.4 Frequency dictionary
def build_freq_dict(filename):
    freq = {}
    with open(filename, encoding='utf-8') as f:
        for line in f:
            w = line.strip()
            freq[w] = freq.get(w, 0) + 1
    return freq

# 2.5 PhoneBook using dict
class PhoneBook:
    def __init__(self):
        self._book = {}
    def add(self, name, number):
        self._book[name] = number
    def get(self, name):
        return self._book.get(name)
    def remove(self, name):
        self._book.pop(name, None)

# Пример измерений
if __name__ == "__main__":
    arr = [random.randint(0,1000000) for _ in range(1000000)]
    x = arr[len(arr)//2]
    # Binary vs Linear timing
    t0 = time.time()
    linear_search(arr, x)
    print("Linear:", time.time()-t0)
    arr.sort()
    t0 = time.time()
    binary_search_iter(arr, x)
    print("Binary iter:", time.time()-t0)
    t0 = time.time()
    binary_search_rec(arr, x)
    print("Binary rec:", time.time()-t0)

    # 2.5 PhoneBook test
    pb = PhoneBook()
    names = [f"user{i}" for i in range(100000)]
    nums = [str(random.randint(1000000,9999999)) for _ in names]
    for n, num in zip(names, nums):
        pb.add(n, num)
    t0 = time.time()
    for _ in range(100000):
        pb.get(random.choice(names))
    print("PhoneBook lookup avg:", (time.time()-t0)/100000)

Рекурсия и рекурсивные алгоритмы

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

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

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

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

Это различие имеет свои плюсы и минусы:

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

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

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

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

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

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

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

Факториал числа

Давайте рассмотрим пример с вычислением факториала. Факториал числа n (обозначается n!) – это произведение всех натуральных чисел от 1 до n. Например, 5! = 5 * 4 * 3 * 2 * 1 = 120. Вычисление факториала рекурсивно выглядит так:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

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

Рекурсия может быть как полезной, так и опасной. Каждый раз, когда вы вызываете функцию, создается новый уровень стека. Если глубина рекурсии слишком велика, это может привести к ошибке переполнения стека. Будьте осторожны и разумно используйте этот подход.

Числа Фибоначчи

Числа Фибоначчи — это последовательность чисел, где каждое последующее число является суммой двух предыдущих. Начинается эта последовательность с нуля и единицы. Получается: 0, 1, 1, 2, 3, 5, 8, 13 и так далее. Это звучит просто, но алгоритм вычисления достаточно интересен.

Можно написать рекурсивный алгоритм для нахождения n-го числа Фибоначчи. Здесь важно учитывать, что этот подход не самый эффективный для больших n из-за повторных вычислений. Вот пример такого алгоритма на Python:

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Более эффективный способ — использовать итерацию. Этот подход не требует глубоких рекурсионных вызовов и работает значительно быстрее:

def fibonacci(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Таким образом, вычисление чисел Фибоначчи может быть реализовано различными способами, и каждый из них имеет свои плюсы и минусы.

Тема 3. Рекурсия и рекурсивные алгоритмы

Контрольные вопросы

Что такое рекурсия и в чём смысл базового (останавливающего) случая?
Чем рекурсивный алгоритм отличается от итеративного? Какие у рекурсии плюсы и минусы?
Что такое «глубина рекурсии» и как она связана со стеком вызовов?
Каковы риски переполнения стека при глубокой рекурсии и как их избежать?
Что такое хвостовая рекурсия и поддерживает ли Python её оптимизацию?

Практические задания

Задание 3.1.
Реализуйте функции:

factorial_rec(n) – рекурсивный расчёт n!;

factorial_iter(n) – итеративный расчёт n!.

Сравните время работы обеих функций для n=500 и измерьте максимальную глубину рекурсии (модуль sys).

Задание 3.2.
Реализуйте:

fib_rec(n) – наивное рекурсивное вычисление n-го числа Фибоначчи;

fib_memo(n) – рекурсия с мемоизацией (кэширование результатов).

Сравните время работы обоих вариантов для n=35.

Задание 3.3.
Напишите рекурсивную функцию flatten(seq), которая «расплющивает» произвольно вложенный список (tuple/list) в плоский список элементов. Пример:
flatten([1, [2,3], (4,[5,[6]]), 7])
# → [1,2,3,4,5,6,7]

Задание 3.4.
Используя рекурсию, реализуйте dir_stats(path), которая обходит все файлы и подпапки в каталоге path и возвращает кортеж (число файлов, общий размер в байтах). Используйте модуль os или pathlib.

Задание 3.5.
Реализуйте классический рекурсивный алгоритм «Ханойские башни». Функция hanoi(n, src, dst, aux) должна возвращать список кортежей (откуда, куда) для переноса n дисков. Проверьте для n=4 и выведите число шагов.

Ответы

3.1.
– Оба дают 500!, но 
  рекурсия глубиной 500 → риск RecursionError,
  итерация – без стека.
– Время примерно одинаково O(n).

3.2.
– fib_rec(35) ≈ O(2^n) ≈ 2^35 вызовов → ~1–2 сек.
– fib_memo(35) – O(n) → мгновенно.

3.3.
flatten([1,[2,3],(4,[5,[6]]),7]) → [1,2,3,4,5,6,7]

3.4.
dir_stats("путь") → (число_файлов, общий_байт)

3.5.
Для n=4 число шагов = 2⁴ − 1 = 15  
Список ходов длины 15.

Решения


import sys
import time
import os
from functools import lru_cache
from pathlib import Path

# 3.1 Factorial
def factorial_rec(n):
    if n <= 1:
        return 1
    return n * factorial_rec(n-1)

def factorial_iter(n):
    result = 1
    for i in range(2, n+1):
        result *= i
    return result

# Сравнение
sys.setrecursionlimit(2000)
n = 500
t0 = time.time()
factorial_rec(n)
print("recursion time:", time.time() - t0, "depth limit:", sys.getrecursionlimit())
t0 = time.time()
factorial_iter(n)
print("iteration time:", time.time() - t0)

# 3.2 Fibonacci
def fib_rec(n):
    if n < 2:
        return n
    return fib_rec(n-1) + fib_rec(n-2)

@lru_cache(None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n-1) + fib_memo(n-2)

# Сравнение
t0 = time.time(); fib_rec(35); print("fib_rec:", time.time() - t0)
t0 = time.time(); fib_memo(35); print("fib_memo:", time.time() - t0)

# 3.3 Flatten
def flatten(seq):
    out = []
    for el in seq:
        if isinstance(el, (list, tuple)):
            out.extend(flatten(el))
        else:
            out.append(el)
    return out

# 3.4 Dir stats
def dir_stats(path):
    total_files = 0
    total_size = 0
    for entry in os.scandir(path):
        if entry.is_file():
            total_files += 1
            total_size += entry.stat().st_size
        elif entry.is_dir():
            f, s = dir_stats(entry.path)
            total_files += f
            total_size += s
    return total_files, total_size

# 3.5 Tower of Hanoi
def hanoi(n, src, dst, aux):
    if n == 0:
        return []
    moves = []
    moves += hanoi(n-1, src, aux, dst)
    moves.append((src, dst))
    moves += hanoi(n-1, aux, dst, src)
    return moves

# Пример для n=4
moves = hanoi(4, 'A', 'C', 'B')
print("Hanoi moves count:", len(moves))
print("Moves:", moves)

Тема 3. Рекурсия и рекурсивные алгоритмы

Контрольные вопросы

Что такое рекурсия и в чём смысл базового (останавливающего) случая?
Чем рекурсивный алгоритм отличается от итеративного? Какие у рекурсии плюсы и минусы?
Что такое «глубина рекурсии» и как она связана со стеком вызовов?
Каковы риски переполнения стека при глубокой рекурсии и как их избежать?
Что такое хвостовая рекурсия и поддерживает ли Python её оптимизацию?

Практические задания

Задание 3.1.
Реализуйте функции:

factorial_rec(n) – рекурсивный расчёт n!;

factorial_iter(n) – итеративный расчёт n!.

Сравните время работы обеих функций для n=500 и измерьте максимальную глубину рекурсии (модуль sys).

Задание 3.2.
Реализуйте:

fib_rec(n) – наивное рекурсивное вычисление n-го числа Фибоначчи;

fib_memo(n) – рекурсия с мемоизацией (кэширование результатов).

Сравните время работы обоих вариантов для n=35.

Задание 3.3.
Напишите рекурсивную функцию flatten(seq), которая «расплющивает» произвольно вложенный список (tuple/list) в плоский список элементов. Пример:
flatten([1, [2,3], (4,[5,[6]]), 7])
# → [1,2,3,4,5,6,7]

Задание 3.4.
Используя рекурсию, реализуйте dir_stats(path), которая обходит все файлы и подпапки в каталоге path и возвращает кортеж (число файлов, общий размер в байтах). Используйте модуль os или pathlib.

Задание 3.5.
Реализуйте классический рекурсивный алгоритм «Ханойские башни». Функция hanoi(n, src, dst, aux) должна возвращать список кортежей (откуда, куда) для переноса n дисков. Проверьте для n=4 и выведите число шагов.

Ответы

3.1.
– Оба дают 500!, но 
  рекурсия глубиной 500 → риск RecursionError,
  итерация – без стека.
– Время примерно одинаково O(n).

3.2.
– fib_rec(35) ≈ O(2^n) ≈ 2^35 вызовов → ~1–2 сек.
– fib_memo(35) – O(n) → мгновенно.

3.3.
flatten([1,[2,3],(4,[5,[6]]),7]) → [1,2,3,4,5,6,7]

3.4.
dir_stats("путь") → (число_файлов, общий_байт)

3.5.
Для n=4 число шагов = 2⁴ − 1 = 15  
Список ходов длины 15.

Решения


import sys
import time
import os
from functools import lru_cache
from pathlib import Path

# 3.1 Factorial
def factorial_rec(n):
    if n <= 1:
        return 1
    return n * factorial_rec(n-1)

def factorial_iter(n):
    result = 1
    for i in range(2, n+1):
        result *= i
    return result

# Сравнение
sys.setrecursionlimit(2000)
n = 500
t0 = time.time()
factorial_rec(n)
print("recursion time:", time.time() - t0, "depth limit:", sys.getrecursionlimit())
t0 = time.time()
factorial_iter(n)
print("iteration time:", time.time() - t0)

# 3.2 Fibonacci
def fib_rec(n):
    if n < 2:
        return n
    return fib_rec(n-1) + fib_rec(n-2)

@lru_cache(None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n-1) + fib_memo(n-2)

# Сравнение
t0 = time.time(); fib_rec(35); print("fib_rec:", time.time() - t0)
t0 = time.time(); fib_memo(35); print("fib_memo:", time.time() - t0)

# 3.3 Flatten
def flatten(seq):
    out = []
    for el in seq:
        if isinstance(el, (list, tuple)):
            out.extend(flatten(el))
        else:
            out.append(el)
    return out

# 3.4 Dir stats
def dir_stats(path):
    total_files = 0
    total_size = 0
    for entry in os.scandir(path):
        if entry.is_file():
            total_files += 1
            total_size += entry.stat().st_size
        elif entry.is_dir():
            f, s = dir_stats(entry.path)
            total_files += f
            total_size += s
    return total_files, total_size

# 3.5 Tower of Hanoi
def hanoi(n, src, dst, aux):
    if n == 0:
        return []
    moves = []
    moves += hanoi(n-1, src, aux, dst)
    moves.append((src, dst))
    moves += hanoi(n-1, aux, dst, src)
    return moves

# Пример для n=4
moves = hanoi(4, 'A', 'C', 'B')
print("Hanoi moves count:", len(moves))
print("Moves:", moves)

Жадные алгоритмы и их применение

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

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

Предположим, у нас есть следующие монеты: 1 рубль, 3 рубля и 4 рубля. Нам необходимо разменять 6 рублей.

На первом этапе мы выбираем самую крупную монету, которая не превышает оставшуюся сумму. В данном случае это 4 рубля. — Оставшаяся сумма: 6 — 4 = 2 рубля. — Используемые монеты: 4 рублей.
Теперь у нас осталось 2 рубля. Опять выбираем самую крупную монету, которая не превышает эту сумму, что, в данном случае, будет 1 рубль. — Оставшаяся сумма: 2 — 1 = 1 рубль. — Используемые монеты: 4 рублей, 1 рубль.
На последнем шаге у нас осталась сумма в 1 рубль, и мы можем взять еще одну монету в 1 рубль. — Оставшаяся сумма: 1 — 1 = 0 рублей. — Используемые монеты: 4 рублей, 1 рубль, 1 рубль.
Таким образом, для размена 6 рублей мы использовали следующие монеты: 4 рубля + 1 рубль + 1 рубль. Всего 3 монеты.

Шаг 1: Используем 4 рубля Сумма: 6 (надпись: -4) _________ | 4 | |_________| Остаток: 2

Шаг 2: Используем 1 рубль Сумма: 2 (надпись: -1) _________ | 1 | |_________| Остаток: 1

Шаг 3: Используем еще 1 рубль Сумма: 1 (надпись: -1) _________ | 1 | |_________| Остаток: 0 Итог: 4 + 1 + 1 = 6

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

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

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

Код Хаффмана — это алгоритм сжатия данных, использующий префиксные коды для представления символов, в зависимости от их частоты появления в тексте.

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

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

Задача о рюкзаке

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

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

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

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

Пример реализации алгоритма на языке Python выглядит следующим образом:

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w - weights[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]

weights = [1, 2, 3]
values = [10, 15, 40]
capacity = 6
print(knapsack(weights, values, capacity))  # Вывод: 55

Также можно визуализировать этот процесс. Рассмотрим следующий ASCII-дизайн, который иллюстрирует работу алгоритма:

Таблица dp (предметы = строки, вес = столбцы):
   0  1  2  3  4  5  6
0  0  0  0  0  0  0  0
1  0 10 10 10 10 10 10
2  0 10 15 15 25 25 25
3  0 10 15 15 25 30 55

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

Задания и вопросы. Тема 4 . Жадные алгоритмы и их применение

Контрольные вопросы

Что такое жадный (greedy) алгоритм? В чём суть «жадного выбора»?
Как отличить задачи, где жадный алгоритм даёт оптимальное решение, от тех, где нет?
Приведите пример «канонической» монетной системы, где жадный алгоритм для размена монет работает.
В чём состоит жадное решение задачи о непрерывном рюкзаке (fractional knapsack)?
Почему для построения кода Хаффмана используется жадный алгоритм? Какова его структура?

Практические задания

Задание 4.1. Размен монет (canonical coin change).
Даны монеты номиналом [1,5,10,25] центов. Напишите функцию min_coins(amount), возвращающую минимальное число монет для заданной суммы amount и список номиналов этих монет, используя жадный алгоритм.

Задание 4.2. Непрерывный рюкзак (fractional knapsack).
Дан рюкзак ёмкостью W и список предметов [(value, weight), …]. Реализуйте жадный алгоритм fractional_knapsack(W, items), который возвращает максимальную стоимость, заполняя рюкзак дробными частями предметов в порядке убывания value/weight.

Этот подход основан на том, что важно максимально эффективно использовать доступное пространство рюкзака, выбирая сначала самые «ценные» предметы, которые обеспечивают наибольшую стоимость на единицу веса.

Для более полного понимания задачи рассмотрим несколько примеров.

1. Предположим, у нас есть рюкзак с ёмкостью W = 50 и список предметов: items = [(60, 10), (100, 20), (120, 30)].

Здесь первый элемент представляет собой предмет с ценностью 60 и весом 10, второй — с ценностью 100 и весом 20, третий — с ценностью 120 и весом 30.

В данном случае, следует сначала взять первый предмет (60/10 = 6.0), затем второй (100/20 = 5.0), и, наконец, взять часть третьего предмета, чтобы заполнить рюкзак до максимума.

В результате, максимальная стоимость, которую мы можем получить, составит 240.

2. Другой пример может включать рюкзак с ёмкостью W = 70 и предметы: items = [(100, 20), (60, 10), (120, 30), (80, 40)].

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

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

Задание 4.3. Расписание занятий (interval scheduling).
Дан список пар (start, end) — время начала и окончания занятий. Напишите функцию max_non_overlapping(intervals), которая жадно выбирает максимально возможное число непересекающихся занятий, сортируя по окончанию.

Задание 4.4. Код Хаффмана (Huffman coding).
Дана строка s. Реализуйте жадный алгоритм Хаффмана: строите дерево, выбирая два наименьших по частоте узла на каждом шаге. Функция huffman_code(s) должна вернуть словарь кодов символов и суммарную длину закодированной строки в битах.

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

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

Коды символов формируются путем прохождения по дереву: для каждого левого ребра добавляется «0», а для правого — «1».

Пример работы функции может выглядеть так:

Входные данные: s = "hello huffman" Частоты: h: 2, e: 1, l: 2, o: 1, u: 1, f: 2, m: 1, a: 1, n: 1

После завершения алгоритма, функция huffman_code(s) может вернуть следующий словарь кодов символов: {'h': '00', 'e': '1110', 'l': '01', 'o': '110', 'u': '1111', 'f': '10', 'm': '1101', 'a': '11101', 'n': '11100'}

Суммарная длина закодированной строки: 78 бит.

Задание 4.5. Покрытие отрезков (set cover special case).
Дано множество точек на прямой и список отрезков. Напишите жадный алгоритм min_segments(points, segments), который выбирает минимальное число отрезков, покрывающих все точки, на каждом шаге беря отрезок, покрывающий наибольшее число ещё непокрытых точек.

Ответы

1. min_coins(63) → 25+25+10+1+1+1 = 6 монет.

2. fractional_knapsack(50, [(60,10),(100,20),(120,30)]) → взять полностью (60,10),(100,20) и 20/30 от последнего → 
    value = 60+100+(20/30)*120 = 220+80 = 300.

3. max_non_overlapping([(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11)]) → занятия (1,4),(5,7),(8,11) → 3.

4. Для s="abbccc": частоты {a:1,b:2,c:3}, код может быть {'c':'0','b':'10','a':'11'}, суммарная длина = 1*2+2*2+3*1 = 2+4+3 = 9 бит.

5. points=[1,2,3,4,5], segments=[(1,3),(2,5),(4,6)] → берём (2,5) покрывает 2–5, остаётся {1} → берём (1,3) → 2 отрезка.

Решения


# 4.1. Coin change, greedy
def min_coins(amount):
    coins = [25,10,5,1]
    result = []
    for c in coins:
        cnt = amount // c
        amount %= c
        result += [c]*cnt
    return result

# 4.2. Fractional knapsack
def fractional_knapsack(W, items):
    # items = list of (value, weight)
    items = sorted(items, key=lambda x: x[0]/x[1], reverse=True)
    total = 0.0
    for v,w in items:
        if W == 0: break
        take = min(w, W)
        total += take * (v/w)
        W -= take
    return total

# 4.3. Interval scheduling
def max_non_overlapping(intervals):
    intervals = sorted(intervals, key=lambda x: x[1])
    count = 0
    last_end = -1e9
    for s,e in intervals:
        if s >= last_end:
            count += 1
            last_end = e
    return count

# 4.4. Huffman coding
import heapq
from collections import Counter

def huffman_code(s):
    freq = Counter(s)
    heap = [(f, sym) for sym,f in freq.items()]
    heapq.heapify(heap)
    # build tree: represent nodes by (freq, tree)
    # leaf: tree = sym, internal: (left,right)
    while len(heap) > 1:
        f1, t1 = heapq.heappop(heap)
        f2, t2 = heapq.heappop(heap)
        heapq.heappush(heap, (f1+f2, (t1,t2)))
    # generate codes
    def gen(tree, prefix, codes):
        if isinstance(tree, str):
            codes[tree] = prefix
        else:
            left,right = tree
            gen(left, prefix+'0', codes)
            gen(right, prefix+'1', codes)
    _, tree = heap[0]
    codes = {}
    gen(tree, '', codes)
    length = sum(len(codes[ch])*cnt for ch,cnt in Counter(s).items())
    return codes, length

# 4.5. Greedy set cover special case
def min_segments(points, segments):
    pts = set(points)
    chosen = []
    while pts:
        best = max(segments, key=lambda seg: len(pts & set(range(seg[0], seg[1]+1))))
        chosen.append(best)
        pts -= set(range(best[0], best[1]+1))
    return chosen

# Примеры:
print(min_coins(63))            # [25,25,10,1,1,1]
print(fractional_knapsack(50, [(60,10),(100,20),(120,30)]))  # 300.0
print(max_non_overlapping([(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11)]))  # 3
codes,length = huffman_code("abbccc")
print(codes, length)  # e.g. {'c':'0','b':'10','a':'11'} 9
print(min_segments([1,2,3,4,5], [(1,3),(2,5),(4,6)]))  # [(2,5),(1,3)]

Методы оптимизации

Мемоизация

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

Пример реализации мемоизации на Python выглядит так:

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

С помощью мемоизации мы избегаем лишних повторных расчетов, что делает алгоритм более эффективным.

Динамическое программирование

Динамическое программирование — это приём «заполнить табличку» с результатами простых подзадач и собрать из них ответ задачи побольше, чтобы не пересчитывать одно и то же много раз.

Идея проста: когда вы замечаете, что одна и та же маленькая задача (например, «какое число Фибоначчи для n=5?») появляется несколько раз, вы можете запомнить её результат и не считать заново. Часто это удобно делать в таблице или массиве.

Пример 1: числа Фибоначчи «снизу вверх»

Числа Фибоначчи задаются так:

F(0) = 0
F(1) = 1
F(n) = F(n−1) + F(n−2), n≥2

Вместо рекурсии мы заведём массив fib длины n+1 и заполним его подряд:

def fib(n):
    fib = [0] * (n+1)
    fib[0] = 0
    fib[1] = 1
    for i in range(2, n+1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]

print(fib(6))  # 8

Как это выглядит «в цифрах» (для n=6):

i	fib[i]	пояснение
0	0	по определению
1	1	по определению
2	fib[1]+fib[0] = 1+0 = 1
3	fib[2]+fib[1] = 1+1 = 2
4	fib[3]+fib[2] = 2+1 = 3
5	fib[4]+fib[3] = 3+2 = 5
6	fib[5]+fib[4] = 5+3 = 8

Пример 2: максимальная сумма подмассива (Kadane’s алгоритм)

Задача: в массиве arr найти непрерывный подмассив с максимальной суммой.
Подход «снизу вверх»: идём слева направо, храним две переменные:

current_sum — максимальная сумма подмассива, который заканчивается в текущем элементе;
max_sum — лучшая из всех таких сумм за всё время.

def max_subarray(arr):
    max_sum = arr[0]
    current_sum = arr[0]
    for x in arr[1:]:
        # либо начинаем новый подмассив в x, либо продолжаем старый:
        current_sum = max(x, current_sum + x)
        # обновляем лучший ответ:
        max_sum = max(max_sum, current_sum)
    return max_sum

print(max_subarray([-2,1,-3,4,-1,2,1,-5,4]))  # 6 (подмассив [4,-1,2,1])

Таблица шагаем по массиву [-2,1,-3,4,-1,2,1,-5,4]:

i	arr[i]	current_sum = max(arr[i], prev + arr[i])	max_sum = max(prev_max, current_sum)
0	−2	−2	−2
1	1	max(1, −2+1)=1	max(−2,1)=1
2	−3	max(−3,1+−3)=−2	max(1,−2)=1
3	4	max(4,−2+4)=4	max(1,4)=4
4	−1	max(−1,4+−1)=3	max(4,3)=4
5	2	max(2,3+2)=5	max(4,5)=5
6	1	max(1,5+1)=6	max(5,6)=6
7	−5	max(−5,6+−5)=1	max(6,1)=6
8	4	max(4,1+4)=5	max(6,5)=6

Задания и вопросы. Тема. Методы оптимизации алгоритмов.

Контрольные вопросы

Что такое мемоизация? Чем она отличается от классического динамического программирования?
Когда рекурсивный алгоритм выгодно превращать в мемоизированный? Приведите пример.
Что такое «табличное» (bottom-up) ДП и в каких случаях его предпочитают «рекурсивному + мемоизация»?
Как выбрать размер и структуру таблицы для ДП-задачи на разрезы строки или массива?
Назовите две классические задачи, решаемые с помощью динамического программирования.

Практические задания

Задание 5.1. Последовательность Фибоначчи с мемоизацией.
Напишите две функции:

fib_rec(n) — чисто рекурсивно вычисляет n-е число Фибоначчи.

fib_memo(n) — то же, но с мемоизацией (используя словарь или functools.lru_cache).

Сравните время работы обоих для n=35 и выведите результат.

Задание 5.2. Подсчёт путей в сетке (Grid Paths).
Дана прямоугольная сетка m×n. Из вершины (0,0) можно двигаться только вправо или вниз. Напишите:

paths_rec(m,n) — рекурсивно без оптимизации.

paths_dp(m,n) — табличный (bottom-up) ДП, возвращающий число путей до (m,n).

Проверьте, что оба возвращают одинаковое для m=15, n=15.

Задание 5.3. Задача о рюкзаке 0/1.
Дан рюкзак вместимости W и список предметов items = [(value, weight), …]. Реализуйте:

knapsack_rec(i, w) — рекурсивно (без мемоизации) оптимальное значение для первых i предметов и оставшегося веса w.

knapsack_dp(items, W) — таблично, заполняя таблицу размеров (len(items)+1)×(W+1).

Задание 5.4. Подпоследовательность с наибольшей суммой (Max Subarray).
Дан список целых чисел. Напишите алгоритм ДП «Кадане» (max_subarray(arr)), который за один проход накапливает текущую максимальную и глобальную максимальную суммы подпоследовательности.

Задание 5.5 Редакционное расстояние (Levenshtein).
Даны две строки s1 и s2. Постройте решение методом ДП:

Создайте таблицу dp[len(s1)+1][len(s2)+1], где dp[i][j] — минимальное число операций вставки/удаления/замены, чтобы превратить s1[:i] в s2[:j].

Верните dp[len(s1)][len(s2)] для примера s1="kitten", s2="sitting".

Ответы

M1.
fib_rec(35) — ~2.0 секунды 
fib_memo(35) — ~0.0001 секунды

M2.
paths_rec(15,15) = C(30,15) = 155117520
paths_dp(15,15) = 155117520

M3. Для items=[(60,10),(100,20),(120,30)], W=50:
knapsack_rec → 220
knapsack_dp  → 220

M4.
max_subarray([-2,1,-3,4,-1,2,1,-5,4]) → 6  (подпоследовательность [4,-1,2,1])

M5.
dp["kitten","sitting"] = 3  (заменить k→s, e→i, добавить g)

Решения


import time
from functools import lru_cache

# M1. Fibonacci
def fib_rec(n):
    if n < 2: return n
    return fib_rec(n-1) + fib_rec(n-2)

@lru_cache(None)
def fib_memo(n):
    if n < 2: return n return fib_memo(n-1) + fib_memo(n-2) t0 = time.time(); fib_rec(35); print("rec:", time.time()-t0) t0 = time.time(); fib_memo(35); print("memo:", time.time()-t0) # M2. Grid paths def paths_rec(m,n): if m==0 or n==0: return 1 return paths_rec(m-1,n) + paths_rec(m,n-1) def paths_dp(m,n): dp = [[1]*(n+1) for _ in range(m+1)] for i in range(1,m+1): for j in range(1,n+1): dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[m][n] print(paths_rec(15,15), paths_dp(15,15)) # M3. 0/1 Knapsack def knapsack_rec(items, W, i=None): if i is None: i = len(items) if i==0 or W==0: return 0 v,w = items[i-1] if w>W: return knapsack_rec(items,W,i-1)
    return max(knapsack_rec(items,W,i-1),
               knapsack_rec(items,W-w,i-1)+v)

def knapsack_dp(items, W):
    n = len(items)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1,n+1):
        v,w = items[i-1]
        for wt in range(W+1):
            dp[i][wt] = dp[i-1][wt]
            if wt>=w:
                dp[i][wt] = max(dp[i][wt], dp[i-1][wt-w] + v)
    return dp[n][W]

items = [(60,10),(100,20),(120,30)]
print(knapsack_rec(items,50), knapsack_dp(items,50))

# M4. Kadane's algorithm
def max_subarray(arr):
    best = curr = arr[0]
    for x in arr[1:]:
        curr = max(x, curr + x)
        best = max(best, curr)
    return best

print(max_subarray([-2,1,-3,4,-1,2,1,-5,4]))

# M5. Levenshtein distance
def levenshtein(s1,s2):
    m,n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0] = i
    for j in range(n+1): dp[0][j] = j
    for i in range(1,m+1):
        for j in range(1,n+1):
            cost = 0 if s1[i-1]==s2[j-1] else 1
            dp[i][j] = min(
                dp[i-1][j] + 1,   # delete
                dp[i][j-1] + 1,   # insert
                dp[i-1][j-1] + cost  # replace
            )
    return dp[m][n]

print(levenshtein("kitten","sitting"))