ztc16627的专栏

原创 递归函数的复杂度分析

一．前言   递归函数的主要思想是将一个问题分拆为几个子问题（问题大小减少），分别解决这些子问题，再将得到的结果组合起来。所以，递归函数的复杂度包括分拆问题的代价，组合结果的代价（统称称为非递归代价）和解决子问题的代价（递归复杂度）。   递归函数的复杂度分析主要是通过递归方程和递归树进行分析的。首先，将一个递归函数的复杂度表示成递归方程的形式，然后通过数学计算或递归树分析，得到递归函数的近似复杂