Перейти к содержанию

2.6   Упражнения

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

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

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

  1. Переменная цикла i поочередно принимает значения 1, 2, 3, 4, а s после каждой итерации становится равной 1, 3, 6, 10. Поэтому sum_iter(4) возвращает 10.

  2. Функции вызываются в следующем порядке: 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 вызова функции еще не завершены.

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

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

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

Во всех трех фрагментах кода входные данные — положительное целое число \(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\), поэтому сложность квадратичная.

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

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

  1. создать новый массив res той же длины, скопировать в него элементы в обратном порядке и вернуть его;

  2. задать два индекса i и j, перемещать их от начала и конца массива к середине и попарно менять местами nums[i] и nums[j].

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

Ответ

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

  2. Используются только две индексные переменные, поэтому пространственная сложность равна \(O(1)\), а операция выполняется на месте.

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

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

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

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

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

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

LeetCode

Оставляйте свои идеи, вопросы и предложения в комментариях