Сложность для рекурсивных функций - время и пространство

Question

Мне было интересно узнать, как рассчитать временную и пространственную сложность рекурсивных функций, таких как перестановка, Фибоначчи (описано здесь )

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

Спасибо

Answer 1

Взгляните на http://www.cs.duke.edu/~ola/ap/recurrence.html

Answer 2

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

Рассмотрим алгоритм двоичного поиска (Поиск элемента в массиве): каждый раз, когда средний элемент (средний) выбирается и сравнивается с элементом (x), который нужно найти. Если (середина> x), искать нижний подмассив, иначе искать верхний подмассив. Если в массиве n элементов, и пусть T (n) представляет временную сложность алгоритма, то T (n) = T (n / 2) + c, где c - постоянная. С заданными граничными условиями мы можем решить для T (n), в этом случае это будет T (n) = log (n), с T (1) = 1.