递归算法的时间复杂度究竟会是怎样的长尾？

本文共计1164个文字，预计阅读时间需要5分钟。

递归算法的时间复杂度是：\[ T(n)=O(f(n)) \]，它表示随着问题规模n的增大，算法的执行时间增长速率与函数f(n)的增长速率成正比。这称为算法的渐进时间复杂度。

递归算法的时间复杂度是：，它表示随问题规模n的增大，算法的执行时间增长率和f(n)增长率成正比，这称作算法的渐进时间复杂度。

递归算法的时间复杂度

时间复杂度：

一般情况下，算法中基本操作重复的次数就是问题规模n的某个函数f（n），进而分析f（n）随n的变化情况并确定T（n）的数量级。这里用‘o’来表示数量级，给出算法时间复杂度。

T（n）=o（f（n））；

它表示随问题规模n的增大，算法的执行时间增长率和f（n）增长率成正比，这称作算法的渐进时间复杂度。而我们一般情况下讨论的最坏的时间复杂度。

推荐课程：C语言教程

空间复杂度：

算法的空间复杂度并不是实际占用的空间，而是计算整个算法空间辅助空间单元的个数，与问题的规模没有关系。算法的空间复杂度S（n）定义为该算法所耗费空间的数量级。

S（n）=o（f（n））

若算法执行所需要的辅助空间相对于输入数据n而言是一个常数，则称这个算法空间复杂度辅助空间为o（1）；

递归算法空间复杂度：递归深度n*每次递归所要的辅助空间，如果每次递归所需要的辅助空间为常数，则递归空间复杂度o（n）。