复杂的递归函数 - 时间和空间

我想知道如何计算我们可以递归的时间和空间像排列，斐波那契（描述here）复杂的递归函数 - 时间和空间

一般递归函数的复杂性，在许多地方，不仅仅是在permutaion或递归，所以我在寻找方法通常遵循计算tmie ANS空间复杂度

谢谢

2010-12-01 daydreamer

看看http://www.cs.duke.edu/~ola/ap/recurrence.html

2010-12-01 16:45:52 NPE

时间复杂度和空间复杂度是表征算法性能的两件事情。现在，由于空间相对便宜，人们主要关心时间复杂性，而时间复杂性主要是用递归关系表示的。考虑二元搜索算法（搜索数组中的元素）：每次选择中间元素（mid）并与要搜索的元素（x）进行比较。如果（mid> x），则搜索较低的子数组，否则搜索较高的子数组。如果一个数组中有n个元素，设T（n）表示算法的时间复杂度，那么T（n）= T（n/2）+ c，其中c是一个常数。对于给定的边界条件，我们可以求解T（n），在这种情况下，它将是T（n）= log（n），其中T（1）= 1.

来源

2010-12-01 17:44:18 anup

答案在这里用视觉来解释：http： //2cupsoftech.wordpress.com/2012/10/31/calculating-time-complexity-of-binary-or-recursive-tree/ – 2cupsOfTech 2012-11-01 22:00:14

复杂的递归函数 - 时间和空间

回答

相关问题