递归函数的复杂性 - 时间和空间
我有兴趣知道如何计算递归函数的时间和空间复杂度，如排列、斐波那契（描述这里）
一般来说，我们可以在很多地方进行递归，而不仅仅是排列或递归，所以我正在寻找通常遵循的方法来计算 tmie ans 空间复杂度
谢谢
I was interested in knowing how to calculate the time and space complexity of recursive functions like permutation, fibonacci(described here)
In general we can have recursion at many places than just at permutaion or recursion, so I am looking for approach generally followed to calculate tmie ans space complexity
Thank you
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
看看 http://www.cs.duke.edu/~ ola/ap/recurrence.html
Take a look at http://www.cs.duke.edu/~ola/ap/recurrence.html
时间复杂度和空间复杂度是表征算法性能的两个因素。如今，由于空间相对廉价，人们最关心的是时间复杂度，而时间复杂度大多用递归关系来表达。
考虑二分搜索算法（搜索数组中的元素）：每次选择中间元素（mid）并将其与要搜索的元素（x）进行比较。如果(mid > x)，则搜索下层子数组，否则搜索上层子数组。如果数组中有n个元素，设T(n)表示算法的时间复杂度，则
T(n) = T(n/2) + c，其中 c 是常数。在给定的边界条件下，我们可以求解 T(n)，在这种情况下，它将是 T(n) = log(n)，其中 T(1) = 1。
Time complexity and space complexity are the two things that characterize the performance of an algorithm. Nowadays, as space is relatively inexpensive, people bother mostly about time complexity, and time complexity is mostly expressed in terms of a recurrence relation.
Consider binary search algorithm (Search for an element in an array): Each time middle element(mid) is selected and compared with the element(x) to be searched. If (mid > x), search the lower sub-array, otherwise search the upper sub-array. If there are n elements in an array, and let T(n) represents the time complexity of the algorithm, then
T(n) = T(n/2) + c, where c is a constant. With given boundary conditions, we can solve for T(n), in this case, it would be T(n) = log(n), with T(1) = 1.