Экспоненциальное время O(2ⁿ) в Go

Когда работа удваивается

O(2ⁿ) означает экспоненциальное время: один лишний элемент на входе удваивает объём работы. Это тот класс роста, в котором алгоритмы перестают быть пригодными — и не для огромных входных данных, а уже для средних.

Экспоненциальная работа обычно берётся из ветвящейся рекурсии: функция вызывает саму себя дважды, и каждый из этих вызовов снова вызывает себя дважды. Вызовы образуют дерево, которое удваивается на каждом уровне.

Числа Фибоначчи через рекурсию

Последовательность Фибоначчи начинается с 0, 1, и каждое следующее число — это сумма двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13, …

Определение напрямую переводится в рекурсивную функцию: fib(n) возвращает fib(n-1) + fib(n-2). Она короткая и правильная — и экспоненциальная, потому что каждый вызов порождает ещё два, и одни и те же значения вычисляются снова и снова. Один только fib(2) внутри вызова побольше пересчитывается тысячи раз.

Числа Фибоначчи с рекурсией

Глобальный счётчик считает каждый вызов. Вычисление fib(10) = 55 занимает 177 вызовов — ради одного маленького числа. Дерево вызовов удваивается на каждом уровне.

Напишите программу на Go с рекурсивной функцией fib (fib от n — это fib от n-1 плюс fib от n-2, а n меньше 2 возвращается как есть), которая при каждом вызове увеличивает глобальный счётчик вызовов. Вычислите fib(10) и выведите результат и общее количество вызовов.

> Вывод: программа на Go и захваченный вывод

Prompt

Напишите программу на Go с рекурсивной функцией fib (fib от n — это fib от n-1 плюс fib от n-2, а n меньше 2 возвращается как есть), которая при каждом вызове увеличивает глобальный счётчик вызовов. Вычислите fib(10) и выведите результат и общее количество вызовов.

Вывод: программа на Go и захваченный вывод

package main

import "fmt"

var calls = 0

func fib(n int) int {
  calls++
  if n < 2 {
    return n
  }
  return fib(n-1) + fib(n-2)
}

func main() {
  fmt.Println("fib(10) =", fib(10))
  fmt.Println("вызовов функции:", calls)
}

Почему это взрывается

Посмотрите на число вызовов, пока n растёт шагами по 5. Оно растёт не шагами — оно умножается. Каждый +1 к n — это примерно ×1,6 к числу вызовов; каждые +5 — больше чем ×10.

При n = 50 счётчик перевалил бы за 40 миллиардов вызовов. В этом и есть экспоненциальная ловушка: код выглядит безобидно, а маленькие тесты завершаются мгновенно.

Считаем вызовы по мере роста n

От fib(5) до fib(25) вход вырастает в 5 раз — а число вызовов вырастает более чем в 16 000 раз, с 15 до 242 785.

Напишите программу на Go с рекурсивной функцией fib, которая считает свои вызовы в глобальном счётчике. Для n = 5, 10, 15, 20, 25 обнуляйте счётчик, запускайте fib(n) и выводите по одной выровненной строке на каждое n с количеством вызовов, чтобы показать экспоненциальный рост.

> Вывод: программа на Go и захваченный вывод

Prompt

Напишите программу на Go с рекурсивной функцией fib, которая считает свои вызовы в глобальном счётчике. Для n = 5, 10, 15, 20, 25 обнуляйте счётчик, запускайте fib(n) и выводите по одной выровненной строке на каждое n с количеством вызовов, чтобы показать экспоненциальный рост.

Вывод: программа на Go и захваченный вывод

package main

import "fmt"

var calls = 0

func fib(n int) int {
  calls++
  if n < 2 {
    return n
  }
  return fib(n-1) + fib(n-2)
}

func main() {
  for _, n := range []int{5, 10, 15, 20, 25} {
    calls = 0
    fib(n)
    fmt.Printf("fib(%2d) -> %7d вызовов\n", n, calls)
  }
}

Решение: цикл

Проблема не в числах Фибоначчи — проблема в том, что одни и те же значения вычисляются снова и снова. Цикл, который идёт вверх от 0 и 1 и хранит только два последних значения, вычисляет каждое число ровно один раз.

Это O(n) по времени и O(1) по памяти: 24 шага вместо 242 785 вызовов для fib(25). Тот же ответ, другой класс роста — именно для этого и нужен анализ алгоритмов.

Числа Фибоначчи с циклом

Две переменные шагают вверх по последовательности; каждый круг вычисляет одно новое число. fib(25) = 75025 за 24 шага — рекурсивной версии для того же ответа понадобилось 242 785 вызовов.

Напишите программу на Go, которая вычисляет fib(25) циклом, а не рекурсией: храните два последних значения в двух переменных и идите вверх от 0 и 1, считая шаги цикла. Выведите результат и количество шагов.

> Вывод: программа на Go и захваченный вывод

Prompt

Напишите программу на Go, которая вычисляет fib(25) циклом, а не рекурсией: храните два последних значения в двух переменных и идите вверх от 0 и 1, считая шаги цикла. Выведите результат и количество шагов.

Вывод: программа на Go и захваченный вывод

package main

import "fmt"

func main() {
  n := 25
  steps := 0

  a, b := 0, 1
  for i := 2; i <= n; i++ {
    a, b = b, a+b
    steps++
  }

  fmt.Println("fib(25) =", b)
  fmt.Println("шагов цикла:", steps)
}