递归 - 时间复杂度
在本文中, 我们主要介绍如何分析递归算法程序中的时间复杂度。.
在一个递归程序中, 它的时间复杂度 O(T) 一般来说就是他总共递归调用的次数 (定义为 R) 以及每次调用时所花费的耗时 (定义为 O(s)) ,这样我们就可以得出:(T) = R * O(T) = R∗O(s)
下面让我们来看几个栗子:
线性的栗子
正如之前的问题 printReverse所描述的, 需要把一个字串逆序输出. 其中一种递归的解法如下所示:
printReverse(str) = printReverse(str[1...n]) + print(str[0])
其中 str[1...n] 是输入的字串 str 去除了首字母str[0]的切分子串, .
显而易见,这个算法会连续调用 n 次, 这个 n 也就该输入字串的长度. 在每次递归的最后, 我们只打印首字母, 因此该算法每次调用递归所耗费的时间为常量, 即为 {\mathcal{O}(1)}O(1).
把次数和每次耗时进行合计,该递归程序 printReverse(str) 的耗时即为 (printReverse) = n * O(1) = O(printReverse)=n∗O(1)=O(n).
执行树
对于递归函数, 像上面的线性化递归调用的栗子其实是很少的,更多的是非线性的. 例如, 之前章节我们讨论的 Fibonacci number ,它的递归关系就定义为更复杂的 f(n) = f(n-1) + f(n-2). 乍看之下, 很难一下子去计算出斐波那契函数的递归调用次数 -_-.
在这个例子里, 我们最好使用 execution tree 这个工具可以用来直观地表示递归程序的执行流. 树中的每一个节点都表示每次对应的递归程序调用. 因此,树中的节点总数与整个递归过程调用的总数相对应。
递归函数的执行树会形成一个 n-ary tree, 其中n 就是这个程序执行下来递归调用的次数. 例如, 斐波那契函数的执行流就是一个二叉树, 如下图所示就是计算 f(4) 的流程树:
在一个 n 层的满二叉树, 所有节点数总和应该是 ![]()
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAD8AAAAfCAYAAABQ8xXpAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAAAHNSURBVFhH7Zevk4JAFMfv79yyhULZQiFtoVgsFhKFQqZQSBSKhUIxUSwUCoX0vbfceq43h+IMI47sZ2ZHnzLP/ezP5xc2jJXfKlZ+q1j5rWLlt4qVn+RcIJQehHDAHQ+HvEGvv1KcEgGHM8ikQB4nyNIQ0otRmw+twDDoNw+Ylm9zSBHjpMO+iuAyBjeqbwbgnAowL8VZx1VIg5F3OnoxQ4s6CcCpj3OYkB9wPHAEhSmhPmNgzEN2MSXaXIIZP1ZHSr7V0WvojhGkL+DvAng0QWZ/7jEhXyPiPrI/DqMoJTdn9h3kr1C/F5FXSXiIytg/V/mr3AfKt8glJ/k9yt8Nfln2HGbuD5RXDLenZlcgUImNw+1chtgJGiQ3QFjWqLMDfDr9ub9HVBoHw8t4Uv5ymt+npxl1aSVIrDaps3hSfo5MX9M1R+Jps9AF3jWoqmpmazD/4nxSPn20OtV9v6S44l3k9ev/9JRM+IhPhnh7RL52CTfJk/LHyVKwQ7kTdLLfivblDmGlg7djoZlXVxjnDtX14qY5XODhVlmNReR1kn/bAdOrZSVOiZ4c+gM29pHDHeM9zAp9rElkTlXMD/f3/Idj5beKld8qVn6bAN9I4KzXzlsT6wAAAABJRU5ErkJggg==)
2^n - 1
. 因此, 对于递归程序 f(n) 总调用次数的上限也应该是 ![]()
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAD8AAAAfCAYAAABQ8xXpAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAAAHNSURBVFhH7Zevk4JAFMfv79yyhULZQiFtoVgsFhKFQqZQSBSKhUIxUSwUCoX0vbfceq43h+IMI47sZ2ZHnzLP/ezP5xc2jJXfKlZ+q1j5rWLlt4qVn+RcIJQehHDAHQ+HvEGvv1KcEgGHM8ikQB4nyNIQ0otRmw+twDDoNw+Ylm9zSBHjpMO+iuAyBjeqbwbgnAowL8VZx1VIg5F3OnoxQ4s6CcCpj3OYkB9wPHAEhSmhPmNgzEN2MSXaXIIZP1ZHSr7V0WvojhGkL+DvAng0QWZ/7jEhXyPiPrI/DqMoJTdn9h3kr1C/F5FXSXiIytg/V/mr3AfKt8glJ/k9yt8Nfln2HGbuD5RXDLenZlcgUImNw+1chtgJGiQ3QFjWqLMDfDr9ub9HVBoHw8t4Uv5ymt+npxl1aSVIrDaps3hSfo5MX9M1R+Jps9AF3jWoqmpmazD/4nxSPn20OtV9v6S44l3k9ev/9JRM+IhPhnh7RL52CTfJk/LHyVKwQ7kTdLLfivblDmGlg7djoZlXVxjnDtX14qY5XODhVlmNReR1kn/bAdOrZSVOiZ4c+gM29pHDHeM9zAp9rElkTlXMD/f3/Idj5beKld8qVn6bAN9I4KzXzlsT6wAAAABJRU5ErkJggg==)
{2^n -1}
. 所以, 我们得出了递归程序 f(n) 的时间复杂度即为 ![]()
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAADYAAAAcCAYAAAAqckyNAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAAAMhSURBVFhH7Zit06MwEMbv74yJwWBiMFUYDKYGg8JgqjEYFAaDicFU1dTU1GBQz20CHB9Jeem1nZv35n1mOtPQEPa3u9ks/YX/VD9g300/YN9NHwS7oQhDFLdh+FbdUcfR5tofAmvRJAckTTuMZ7qWiH0PQjjgjoeouNDsSeeTgMMZ/FOJIj0hz2L4Xgpjqa5BIkJU92G80jZYe0Fx9BCW5Br6XsYBXHooYwzcC5GdLYaT2joCj+qFwVq3Ar5IcR6GrUzg0lpu0izmXjMB5mW4DmMZE2hhEnQN3R9WFD9TD8HudUxePaKk1dtzigOnCJQSUlbIjwKcDGLct6TDFZnnIB2t/6MOdcQRlHMz1DXlKA/5SEG6FT4YwY5qEgVmy7srcuuzHoDdigDcTfrwKy9zd3VzS150dOSc9arkBEdM3p5EqUPOyVf2aQhaZx6R/WCElns6O7phPMoAa1V4mT8YcEbqWoxXUgAqaqtFm4SDz4yaRGA6yjHk7IYJbDL8GbDejgj1imwFtgRpqxD8cIJ1K6lIGmCUhoIhrKw3oPA5gR0x/TymIqdCM1wiPQXW1YiYmY4LsE5tesskqwawZTQlYrpmDZhWh27u2XuJQDlnViiuVYxQkAPcAHHVoMkj2t9UrA5HJJWZ4DoYjunMBZiqPoxRqgzjTclYezqa54CGtRUUm9SR4D4oQM9IZYIZ0RlYP4ExKhrDlS2dUyoezlS6tZ4A03uZoLKLLW2fUW/3ug5YwOjQ++pZ9wohV9FaTdwLpua9BUrpS7AWVdhvZMPghdRC3DhUtfaAtapjONA+nt19q1HYupRd6sE2UlHt5YDACI7OMGl7DnUfeeBA2KCUdIXaKh53cp4wWi1VfeNdG9umHcVjjIaG49RKUb8mpeo2JMpTCM8lT8utcGyVexVQH5yTY4RYfBwukNkK3h7tKfe97pAKwhkByZAgQlZdrD3ZWl8e0NaPecDuljqguVnwLGCvSZ+F1pbqM9rdUr0u1b3sPORf1pNN8Kt6+NryZv3Va8tr2njRfJf0iybtzQeP+BCYElXY/++vgX+vH7DvJeA3tPdQ+X3NjwkAAAAASUVORK5CYII=)
{\mathcal{O}(2^n)}
记忆化
在前面的章节中, 我们讨论过用来优化递归算法时间复杂度的记忆化方法. 通过存储和重复使用中间变量, 记忆化能够极大地降低递归程序的调用次数, 换个说法就是减少执行树中的递归调用分支. 在分析试用了记忆化的递归调用程序的时间复杂度时,千万要记得考虑这种(分支减少的)情况。.
让我们重新再回看前面斐波那契额数列的栗子. 使用记忆化方法的话,我们每次都将斐波那契额数列在 n.节点下的存储, 于是我们可以确保对于每个节点计算需要的递归调用只需要一次. 而且我们知道斐波那契额数列的递归关系是每个 f(n) 都依赖前一个 n-1 的结果. 最终使得计算 f(n) 只调用 n-1 次 之前已经计算好的结果即可.
现在, 我们可以很轻易的通过前面介绍的公式 O(1)∗n=O(n) .来计算斐波那契额数列函数的时间复杂度。记忆化不仅仅优化算法的时间复杂度,同样也简化了对于时间复杂度的计算。
在下一篇文章中, 我们将讨论如何估算递归程序的空间复杂度.
原文地址:https://leetcode.com/explore/learn/card/recursion-i/256/complexity-analysis/1669/