Skip to content

Latest commit

 

History

History
335 lines (232 loc) · 19.8 KB

lesson8.md

File metadata and controls

335 lines (232 loc) · 19.8 KB
Raw

Лекция 8. Рекурсия. Алгоритмы. Бинарный поиск, сортировки

Рекурсия

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

Основные элементы рекурсии

  1. Базовый случай (Base Case): Это условие, при котором рекурсия завершается и функция больше не вызывает саму себя. Без базового случая рекурсивная функция будет вызывать себя бесконечно.

  2. Рекурсивный случай (Recursive Case): Это условие, при котором функция вызывает саму себя для решения более мелкой подзадачи. Рекурсивный случай должен быть сформулирован так, чтобы в конечном итоге привести к базовому случаю.

Пример: Вычисление факториала с использованием рекурсии

Давайте рассмотрим пример рекурсивной функции для вычисления факториала числа. Факториал числа n (обозначается как n!) - это произведение всех положительных целых чисел от 1 до n.

def factorial(n):
    # Базовый случай: факториал 0 или 1 равен 1
    if n == 0 or n == 1:
        return 1
    # Рекурсивный случай: вычисляем факториал для (n-1) и умножаем на n
    else:
        return n * factorial(n - 1)


# Вызываем функцию для вычисления факториала числа 5
result = factorial(5)
print(result)  # Выведет 120, так как 5! = 5 * 4 * 3 * 2 * 1 = 120

Преимущества и ограничения рекурсии

Преимущества:

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

Ограничения:

  • Рекурсия может быть менее эффективной по сравнению с итеративными методами в некоторых случаях из-за накладных расходов на вызов функций.
  • Слишком глубокая рекурсия может вызвать переполнение стека вызовов (stack overflow), что приведет к ошибке.

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

Практика

  1. Напишите рекурсивную функцию вычисления факториала (Да как в примере)
  2. Напишите рекурсивную функцию вычисления n-ого числа Фибоначчи

Введение в алгоритмы. Что такое алгоритмы?

Ремарка

В первую очередь алгоритмы это очень, ОЧЕНЬ большая тема. По ней написаны сотни, если не тысячи книг. Эта тема часто всплывает на собеседованиях. А собеседование в FAANG компании вообще не возможно представить без задач по алгоритмам.

Если вы захотите углубиться в эту тему в первую очередь я рекомендую книгу Грокаем алгоритмы (Grokking Algorithms: An illustrated guide for programmers and other curious people ). Она написано легким стилем и доступна практически каждому.

Более сложная книга Достаточно ли вы умны, что бы работать в Google? (Are You Smart Enough to Work at Google?)

Ну и тяжелая артиллерия, книга которую я могу порекомендовать только если вы уже имеете хотя бы 5 лет коммерческого опыта это Карьера программиста(Cracking the coding interview)

К сути

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

Зачем нужны алгоритмы?

Алгоритмы необходимы для:

  1. Эффективного решения проблем: Они помогают находить решения быстрее и с меньшими затратами ресурсов.
  2. Оптимизации работы программ: Правильный выбор алгоритма может значительно ускорить выполнение программы.
  3. Понимания сложных систем: Изучение алгоритмов помогает понимать, как работают сложные программные системы.
  4. Универсальности: Алгоритмы можно применять в различных областях, таких как обработка данных, машинное обучение, разработка игр и многое другое.

Что такое "О большое"?

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

Основные виды временной сложности:

  • O(1) — Постоянное время: Время выполнения не зависит от размера входных данных.
  • O(log n) — Логарифмическое время: Время выполнения растет логарифмически по мере увеличения входных данных.
  • O(n) — Линейное время: Время выполнения растет линейно по мере увеличения входных данных.
  • O(n log n) — Линейно-логарифмическое время: Время выполнения растет быстрее, чем линейно, но медленнее, чем квадратично.
  • O(n^2) — Квадратичное время: Время выполнения растет квадратично по мере увеличения входных данных.
  • O(2^n) — Экспоненциальное время: Время выполнения растет экспоненциально по мере увеличения входных данных.

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

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

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

У нас есть несколько стратегий для решения этой задачи. Первая это решение в лоб. Мы просто перебираем все варианты от 1 до 100. Но при этом в худшем случае, мы выполним 100 запросов. А что если диапазон будет до 1000? а до 10000000? При таком подходе у нас увеличивается кол-во действий которые нужно сделать вместе с кол-вом данных для которых мы это выполняем. Такие алгоритмы имеют сложность O(n). Увеличение объема данных увеличивает сложность ровно во столько же раз, как и увеличился объем данных.

А можно ли выполнить этот же поиск за меньшее кол-во действий? Можно! Для этого нам поможет бинарный поиск.

Мы можем разделить весь наш интервал пополам, и начать поиск с 50. Узнать что искомый элемент больше. Ок, тогда мы берем середину от оставшихся значений (от 50 до 100) и проверяем 75. И делаем так до тех пор не найдем искомое значение.

Такие алгоритмы имеют сложность O(log n). Для диапазона от 1 до 100, нам понадобится в худшем случае (log 100 == 6,644) 7 попыток. Лучше чем 100, правда? А для диапазона от 1 до 1000 (log 1000 == 9,966) всего 10 попыток! мы увеличили входные данные в 10 раз, а сложность вычисления увеличилась всего в полтора раза!

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

Давай-те посмотрим как это можно реализовать.

Бинарный поиск — это алгоритм для поиска элемента в отсортированном списке. Он работает по принципу "разделяй и властвуй", разделяя массив на половины до тех пор, пока не найдет искомый элемент.

Принцип работы:

  1. Найдите средний элемент списка.
  2. Если средний элемент равен искомому, верните его индекс.
  3. Если искомый элемент меньше среднего, повторите поиск для левой половины списка.
  4. Если искомый элемент больше среднего, повторите поиск для правой половины списка.
  5. Продолжайте до тех пор, пока не найдете элемент или не исчерпаете список.

Пример:

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  # Элемент не найден


# Пример использования
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
print(f"Элемент найден на индексе: {binary_search(arr, target)}")

Или пример через рекурсию:

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1  # Элемент не найден

    mid = (left + right) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)


# Пример использования
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search_recursive(arr, target, 0, len(arr) - 1)

print(f"Элемент найден на индексе: {result}")

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

Огромным пластом алгоритмов являются алгоритмы сортировки. Давайте посмотрим на некоторые из них.

Пузырьковая сортировка (Bubble Sort)

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

Принцип работы:

  1. Сравнивайте каждый элемент списка с его соседним.
  2. Меняйте их местами, если они в неправильном порядке.
  3. Повторяйте процесс до тех пор, пока не будет произведен проход по списку без единой перестановки.

Пример на Python:

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


# Пример использования
arr = [64, 34, 25, 12, 22, 11, 90]
print(f"Отсортированный массив: {bubble_sort(arr)}")

Сортировка слиянием (Merge Sort)

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

Принцип работы:

  1. Разделите массив на две половины.
  2. Рекурсивно отсортируйте каждую половину.
  3. Объедините две отсортированные половины в один отсортированный массив.

Пример на Python:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half)


def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result


# Пример использования
arr = [38, 27, 43, 3, 9, 82, 10]
print(f"Отсортированный массив: {merge_sort(arr)}")

Быстрая сортировка (Quick Sort)

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

Принцип работы:

  1. Выберите опорный элемент (пивот).
  2. Переставьте элементы массива так, чтобы элементы, меньшие пивота, были слева от него, а элементы, большие пивота, были справа.
  3. Рекурсивно примените те же шаги к подмассивам слева и справа от пивота.

Пример на 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)


# Пример использования
arr = [3, 6, 8, 10, 1, 2, 1]
print(f"Отсортированный массив: {quick_sort(arr)}")

Заключение

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

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

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

Нельзя закончить изучать алгоритмы, можно только перестать

Переходим к первому модульному заданию