关于2-1递归空间复杂度
来源：2-1 究竟什么是大O（Big O）
crystal_chen
2018-03-19
老师您好。请教一下：
关于2-1递归空间复杂度最后几十秒钟，严谨来说递归的深度是多少，空间复杂度不一定是多少吗？比方二叉树的结构。这里说的范畴指的只是那个视频最后一个例子？
写回答
1回答
-
你说的例子在视频的具体时间是多少？
对于递归算法来说，递归过程所用的系统栈空间和递归深度是成正比的。但是递归所用的系统栈空间不一定是整个算法的最终的空间复杂度。比如我们递归的最大层数为n，但是整个算法需要开一个n^2的辅助空间，那么这个算法的空间复杂度整体是O(n^2+n)的。n^2是辅助空间的大小;n是递归深度导致产生的系统栈的大小。对于大O符号忽略低阶项，这样一个算法最终的空间复杂度是O(n^2)的。
012018-03-22
相似问题
lc203 递归写法复杂度分析
回答 1
空间，时间复杂度的猜想
回答 1