Вычисление временной сложности в случае алгоритмов рекурсии?

Question

Как рассчитать сложность времени в случае алгоритмов рекурсии?

например, t (n) = t (3n / 2) + 0 (1) (Heapsort)

Answer 1

Используйте Основную теорему .

В любом случае, ваше уравнение выглядит нарушенным, поскольку рекурсивные вызовы имеют более высокие входные значения, чем у вызывающего, поэтому ваша сложность равна O (бесконечность)) .

Пожалуйста, исправьте это.

Answer 2

Мастерская буря - это быстрый и короткий путь. Но так как вы пытаетесь изучить сложность для всех рекурсивных функций, я бы скорее предложил вам изучить работу дерева рекурсии, которое составляет основу The Master's Theorm. Эта ссылка объясняет это подробно. Вместо того, чтобы использовать магическую теорию вслепую, изучите это для лучшего понимания в будущем! Эта ссылка о дереве рекурсии также хорошо читается

Answer 3

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

, но есть теорема, которая решает множество ситуаций в виде кучи, называемая Мастер-теорема:

http://en.wikipedia.org/wiki/Master_theorem

Answer 4

Сложность Heapsort