Упражнения¶

Вопросы для самопроверки¶

Временная и пространственная сложность итерации и рекурсии¶

Обе функции ниже вычисляют \(1 + 2 + \dots + n\) (считайте, что \(n \ge 1\)). Присвойте n значение 4, ответьте на вопросы в порядке фактического выполнения программы, а затем сравните эффективность двух вариантов.

def sum_iter(n):
    s = 0
    for i in range(1, n + 1):
        s += i
    return s

def sum_recur(n):
    if n == 1:
        return 1
    return n + sum_recur(n - 1)

Какие значения принимает переменная s после каждой итерации при выполнении sum_iter(4)?
Какие функции поочередно вызываются при выполнении sum_recur(4)? Как формируется результат при возврате, начиная с самого глубокого вызова?
Каковы временная и пространственная сложности каждого варианта? Обоснуйте ответ, опираясь на процессы выполнения из вопросов 1 и 2.

Ответ

Переменная цикла i поочередно принимает значения 1, 2, 3, 4, а s после каждой итерации становится равной 1, 3, 6, 10. Поэтому sum_iter(4) возвращает 10.
Функции вызываются в следующем порядке: sum_recur(4) → sum_recur(3) → sum_recur(2) → sum_recur(1). sum_recur(1) возвращает 1, после чего следующие уровни поочередно получают 2 + 1 = 3, 3 + 3 = 6 и 4 + 6 = 10. В самой глубокой точке все 4 вызова функции еще не завершены.
В обеих функциях число итераций или вызовов пропорционально \(n\), поэтому их временная сложность равна \(O(n)\). Пространственная сложность различается: итеративный вариант использует постоянное число переменных, поэтому она равна \(O(1)\); в рекурсивном варианте предыдущие вызовы ожидают возврата результата до достижения условия завершения, поэтому в стеке вызовов одновременно хранится до \(n\) вызовов. Его пространственная сложность равна \(O(n)\).

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

Временная сложность трех фрагментов кода¶

Во всех трех фрагментах кода входные данные — положительное целое число \(n\). Расположите фрагменты в порядке возрастания временной сложности и укажите сложность каждого из них.

# Фрагмент 1
s = 0
for i in range(n):
    s += i

# Фрагмент 2
s = 0
for i in range(n):
    for j in range(i, n):
        s += j

# Фрагмент 3
while n > 1:
    n = n // 2

Ответ

Порядок от меньшей сложности к большей: фрагмент 3 — \(O(\log n)\), фрагмент 1 — \(O(n)\), фрагмент 2 — \(O(n^2)\). В фрагменте 3 на каждой итерации \(n\) уменьшается вдвое, поэтому цикл выполняется примерно \(\log_2 n\) раз. Цикл во фрагменте 1 выполняется ровно \(n\) раз. Число итераций внутреннего цикла во фрагменте 2 последовательно равно \(n,n-1,\dots,1\), а их сумма — \(n(n+1)/2\), поэтому сложность квадратичная.

Какой способ разворота экономнее по памяти¶

Все элементы массива nums можно расположить в обратном порядке двумя способами:

создать новый массив res той же длины, скопировать в него элементы в обратном порядке и вернуть его;
задать два индекса i и j, перемещать их от начала и конца массива к середине и попарно менять местами nums[i] и nums[j].

Какова пространственная сложность каждого способа? Какой из них выполняет операцию «на месте»?

Ответ

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

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

Задачи по программированию¶

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

Последовательность Фибоначчи задается так: \(F(0)=0\), \(F(1)=1\), а при \(n\ge2\) выполняется \(F(n)=F(n-1)+F(n-2)\).

Дано неотрицательное целое число n. Вычислите и верните \(F(n)\) с помощью цикла, не используя рекурсию.

Подсказки

Сначала отдельно обработайте случаи, когда n равно 0 или 1
Для вычисления следующего члена нужны только два предыдущих, поэтому хранить всю последовательность не требуется
Обновляя две переменные, не перезапишите слишком рано старое значение, которое еще понадобится

LeetCode