c********t
发帖数: 5706 | 1 请问用了递归以后，怎么计算空间复杂度？
比如说permution和二叉树preorder遍历吧，怎么计算空间复杂度是多少呢 |
w****x
发帖数: 2483 | 2
算法导论上有，比如说斐波那契数列递归的时间复杂度？
【在 c********t 的大作中提到】
: 请问用了递归以后，怎么计算空间复杂度？
: 比如说permution和二叉树preorder遍历吧，怎么计算空间复杂度是多少呢
|
t*********h
发帖数: 941 | 3 把地柜公式写出来就行了吧 比如permutation
T(n)=nT(n-1)+O(n) = O(n!)
【在 c********t 的大作中提到】
: 请问用了递归以后，怎么计算空间复杂度？
: 比如说permution和二叉树preorder遍历吧，怎么计算空间复杂度是多少呢
|
c*****a
发帖数: 808 | |
c********t
发帖数: 5706 | 5 你们说的都是时间复杂度吧？我是问空间怎么算啊？
【在 t*********h 的大作中提到】
: 把地柜公式写出来就行了吧 比如permutation
: T(n)=nT(n-1)+O(n) = O(n!)
|
c*****a
发帖数: 808 | 6 "Whenever the function calls itself recursively all local variables remain
on the stack and a new set of them are pushed to the stack for the new call.
This means that you care how many calls are there at most, in other words
what is the maximum depth of the recursion." |
c********t
发帖数: 5706 | 7 嗯，懂了。看来主要是要计算有多少call。
call.
【在 c*****a 的大作中提到】
: "Whenever the function calls itself recursively all local variables remain
: on the stack and a new set of them are pushed to the stack for the new call.
: This means that you care how many calls are there at most, in other words
: what is the maximum depth of the recursion."
|
