Share This
Связаться со мной
Крути в низ
Categories
//Мемоизация, рекурсия и цикл for в Python

Мемоизация, рекурсия и цикл for в Python

18.05.2021Category : Python

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

Как вы, вероятно, знаете, последовательность Фибоначчи образуется следующим образом. Мы складываем первое и второе число, 0 и 1, чтобы получить третье число в последовательности (0 + 1 = 1). Затем мы складываем второе и третье число, чтобы получить 4-е число в последовательности (1 + 1 = 2). И так проделываем для каждого последующего числа Фибоначчи.

Код, который мы будем рассматривать, вы можете писать в Jupyter, Colab или любой IDE или текстовом редакторе, который вам удобен.

Вычисление n-го члена последовательности Фибоначчи с помощью цикла for

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

Временная сложность решения с помощью цикла for — O(n), а пространственная сложность – O(1) или константа. Правда, на самом деле все несколько сложнее.

«Если ваше число меньше, чем 94, и вы используете 64-битное число, тогда алгоритм ведет себя, как имеющий линейную сложность. Но для N > 94 он начинает вести себя, как алгоритм с квадратичной сложностью», — из ответа Майкла Векслера на сайте Quora.

def fib_for(n):     n1 = 0     n2 = 1     if n <= 0:         return 'Введите число больше 0'     elif n == 1:         return n1     elif n == 2:         return n2     else:         for i in range(2, n):             n1, n2 = n2, n1 + n2         return n2

Запустим этот код с помощью модуля Python %timeit. Это позволит замерить время выполнения, избежав ряда распространенных ловушек.

memoizacija rekursija i cikl for v python c77e55b - Мемоизация, рекурсия и цикл for в Python

Для того, чтобы высчитать 10-е число Фибоначчи, потребовалось по 675 наносекунд на каждую итерацию цикла.

Вычисление n-го члена последовательности Фибоначчи с помощью рекурсии

Теперь давайте реализуем последовательность Фибоначчи с помощью рекурсии. Рекурсивные функции вызывают себя повторно, пока не достигнут базового случая. Таким образом, рекурсия создает древовидную структуру.

Если мы возьмем первые 5 чисел Фибоначчи, то в результате рекурсии получится вот такое дерево.

memoizacija rekursija i cikl for v python 9bfb3d8 - Мемоизация, рекурсия и цикл for в Python

Пространственная сложность в данном случае — O(n), а временная сложность — O(2n). Так происходит, потому что у корневого узла есть 2 дочерних узла (fib(4) и fib(3)) и 4 внука. И, как видите, у каждого узла есть 2 дочерних элемента. Кроме того, вы могли заметить, что правое поддерево меньше, чем левое. Так что, на самом деле время выполнения составляет примерно O(1,6n).

Базовый случай: Fibonacci(2) = Fib(1) + Fib(0)  = 1 + 0 = 1

def fib_recursion(n):     if n <= 0:         return 'Введите число больше 0'     elif n == 1:         return 0     elif n == 2:         return 1     else:         return fib_recursion(n - 1) + fib_recursion(n - 2)

Вычисление n-го члена последовательности Фибоначчи при помощи рекурсии определенно быстрее, чем с помощью цикла for.

memoizacija rekursija i cikl for v python a1d1eba - Мемоизация, рекурсия и цикл for в Python

Вычисление n-го члена последовательности Фибоначчи с использованием мемоизации

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

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

def Fib_memoisation(n, memo):     if n <= 0:         return 'Введите число больше 0'     elif n == 1:         return 0     elif n == 2:         return 1     else:         if n not in memo:             memo[n] = Fib_memoisation(n - 1, memo) + Fib_memoisation(n - 2, memo)         return memo[n]

Временная сложность — O(n * log10n).

memoizacija rekursija i cikl for v python 87c1561 - Мемоизация, рекурсия и цикл for в Python

Что лучше: рекурсия, цикл for или мемоизация?

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

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

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

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

memoizacija rekursija i cikl for v python 420de6d - Мемоизация, рекурсия и цикл for в Python

Свежие вакансии по Python

Для тех, кто хочет найти работу Junior Python Developer

Подписаться ×

  • 7 views
  • 0 Comment

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *

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

Связаться со мной
Close