Практическая работа 1 пара

Практическое занятие №3 «Оценка сложности рекурсивных алгоритмов»

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

Цель работы

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

Короткая теория

Форма рекурсии	Пример рекуррентности	Ожидаемый рост
Один вызов с `n - 1`	`T(n)=T(n-1)+O(1)`	`O(n)`
Один вызов с `n / 2`	`T(n)=T(n/2)+O(1)`	`O(log n)`
Два перекрывающихся вызова	`T(n)=T(n-1)+T(n-2)+O(1)`	экспоненциальный рост

Для рекурсивных функций важно отдельно оценивать время и дополнительную память стека вызовов.

Исходный код

Создайте файл recursion_complexity.py:

from functools import lru_cache
from timeit import repeat


def factorial(n, counter):
    counter[0] += 1

    if n <= 1:
        return 1

    return n * factorial(n - 1, counter)


def recursive_binary_search(a, target, left, right, counter):
    counter[0] += 1

    if left > right:
        return -1

    mid = (left + right) // 2

    if a[mid] == target:
        return mid

    if a[mid] < target:
        return recursive_binary_search(
            a, target, mid + 1, right, counter
        )

    return recursive_binary_search(
        a, target, left, mid - 1, counter
    )


def fibonacci(n, counter):
    counter[0] += 1

    if n <= 1:
        return n

    return (
        fibonacci(n - 1, counter)
        + fibonacci(n - 2, counter)
    )


@lru_cache(maxsize=None)
def fibonacci_cached(n):
    if n <= 1:
        return n

    return fibonacci_cached(n - 1) + fibonacci_cached(n - 2)


def best_time(func):
    return min(repeat(func, repeat=5, number=1))


print("ФАКТОРИАЛ")
for n in [5, 10, 20, 100]:
    counter = [0]
    factorial(n, counter)
    print(n, "вызовов:", counter[0])


print("\nРЕКУРСИВНЫЙ БИНАРНЫЙ ПОИСК")
for n in [10, 100, 1000, 100000]:
    data = list(range(n))
    counter = [0]
    recursive_binary_search(
        data, n + 1, 0, len(data) - 1, counter
    )
    print(n, "вызовов:", counter[0])


print("\nНАИВНЫЙ FIBONACCI")
for n in [5, 10, 20, 30]:
    counter = [0]
    t = best_time(lambda: fibonacci(n, counter))
    print(n, "вызовов:", counter[0], "время:", round(t, 6))


print("\nFIBONACCI С КЭШЕМ")
for n in [5, 10, 20, 30]:
    fibonacci_cached.cache_clear()
    t = best_time(lambda: fibonacci_cached(n))
    print(n, "время:", round(t, 8))

Ход работы

Запустите программу. Для каждой функции зафиксируйте число рекурсивных вызовов.
Для factorial увеличивайте n и определите связь между n и количеством вызовов.
Для recursive_binary_search используйте отсутствующий элемент, чтобы получить близкий к худшему случай. Сравните число вызовов при n = 10, 100, 1000, 100000.
Для fibonacci сравните n = 5, 10, 20, 30. Не увеличивайте значение резко: наивная рекурсия растёт очень быстро.
Сравните наивный Fibonacci и вариант с кэшированием.

Алгоритм	n	Число вызовов	Оценка времени	Оценка памяти стека
factorial	100
binary search	100000
fibonacci	20
fibonacci	30

Задания для анализа

Запишите рекуррентность для factorial и объясните, почему она даёт линейную сложность.
Почему у рекурсивного бинарного поиска глубина растёт логарифмически?
Нарисуйте дерево вызовов fibonacci(5). Отметьте одинаковые подзадачи, которые вычисляются повторно.
Почему кэширование резко ускоряет Fibonacci?
Почему алгоритм может иметь приемлемую временную сложность, но всё равно создавать проблему из-за глубокой рекурсии?

Что показать преподавателю

Код трёх рекурсивных алгоритмов.
Таблицу с количеством вызовов.
Дерево вызовов fibonacci(5).
Рекуррентности и итоговые оценки сложности.
Вывод о влиянии кэширования.

Ориентир по времени

10 минут — разбор рекуррентностей; 40–45 минут — запуск и эксперименты; 20 минут — дерево вызовов и анализ; 5 минут — вывод. Дополнительные 10 минут — исследование кэширования.

Дополнительное задание

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