Возможно, это один из самых известных алгоритмов, но все же многие люди пытаются найти эффективное решение. Позвольте представить вам последовательность Фибоначчи.

Заявление

Учитывая число N, верните значение индекса последовательности Фибоначчи, где последовательность:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

После беглого взгляда вы можете легко заметить, что шаблон последовательности состоит в том, что каждое значение представляет собой сумму 2 предыдущих значений, что означает, что для N = 5 → 2 + 3 или в математике:

F(n) = F(n-1) + F(n-2)

Первая реализация

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

Это, наверное, первое решение, которое придет вам в голову. Здесь важно то, что мы вычисляем следующее число, добавляя текущее число к старому.

И хорошая новость заключается в том, что временная сложность составляет O (n). Достаточно честно для первой попытки, правда? Но давайте попробуем найти другие способы решения проблемы.

Рекурсивное решение

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

Легко, правда? мы просто решили проблему в двух строках кода, но давайте посмотрим глубже и посмотрим, что происходит на самом деле.

Базовый случай: нам просто нужно проверить, меньше ли значение нуля, чтобы вернуть 2 первых случая.

Но теперь плохие новости ... Мы увеличили временную сложность нашего алгоритма почти до наихудшего случая. Если вы посмотрите на график, вы увидите временную сложность оранжевого цвета (2 ^ N), что означает, что наша текущая реализация является экспоненциальной ...

Мемоизация

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

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

Что это означает и почему мы должны позаботиться об этом в нашей реализации? По сути, если мы просто сохраняем значение каждого индекса в хэше, мы избегаем времени вычисления этого значения в следующие N раз.

Это изменение увеличит пространственную сложность нашего нового алгоритма до O (n), но резко снизит временную сложность до 2N, что приведет к линейное время, поскольку 2 - постоянная величина.

Контрольный показатель

Давайте используем 50 в качестве входного числа и посмотрим, как это выглядит:

Цикл пока

  • Сложность времени: O (N)
  • Сложность пространства: Постоянная
  • Вызовы функций: 51
  • Необходимое время: 0,000001 мс

Рекурсия

  • Сложность по времени: O (2 ^ N)
  • Сложность пространства: O (n)
  • Вызов функций: 20.365.011.074
  • Необходимое время: 176,742 мс

Воспоминание

  • Сложность времени: O (2N)
  • Сложность пространства: O (n)
  • Вызовы функций: 99
  • Необходимое время: 0,000001 мс

Результаты JSPerf

Я также создал демонстрацию jsPerf с 3 случаями, вы можете посмотреть здесь:

Заключение

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