数据结构入门咨询：递归函数时间复杂度计算正误及学习资源

你的结论不正确，正确的时间复杂度为O(n²) #

你分析的思路方向是对的，确实需要累加每次递归调用时内部for循环的执行次数，但求和的量级推导出现了错误：

• 调用print(n)时，内部for循环执行n次
• 递归调用print(n-1)时，内部for循环执行n-1次
• 以此类推，直到调用print(0)时直接返回，没有循环操作
  总操作次数为等差数列求和：n + (n-1) + (n-2) + ... + 1 = n(n+1)/2，最高次项为n²，因此时间复杂度是O(n²)，不是O(n)。

入门阶段递归时间复杂度的学习建议 #

你可以先从两种易上手的分析方法开始练：

• 递推展开法：就是你这次用的思路，把每一层递归的操作次数列出来，逐层展开后求和，最后取最高阶的量级即可，适合逻辑简单的递归场景
• 主定理法：是专门用来快速求解分治类递归时间复杂度的公式，归并排序、快速排序这类经典递归算法的复杂度都可以用它快速算出，等你把递推法练熟后可以再学习这个方法。

适合的学习资源 #

你可以参考这些经典教材的对应章节学习：

• 《数据结构与算法分析》系列（选你常用的编程语言版本即可），递归相关章节的案例都是入门级，讲解逻辑友好，容易理解
• 《算法导论》第2-4章，对复杂度分析的基础规则和递归分析方法讲得非常系统，配套的课后习题可以用来巩固练习
• 国内高校常用的严蔚敏版《数据结构》，递归相关内容符合国内学习者的阅读习惯，配套例题很适合入门练手

内容的提问来源于stack exchange，提问作者BrownCoderAyush