递归问题的时间复杂度分析
2017-12-30 17:01:18
递归问题的时间复杂度分析广泛存在于分治法和DP中，根据算法导论的记载，可以使用主定理的公式直接计算。另外，这篇文章介绍一下使用迭代手算的过程。
- 主定理
- 迭代计算
有一点需要说明：2^k*T(n/2^k) = 2^k*T(1) := 2^k*O(1) = n*O(1) = O(n)
版权声明：本文为hyserendipity原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
2017-12-30 17:01:18
递归问题的时间复杂度分析广泛存在于分治法和DP中，根据算法导论的记载，可以使用主定理的公式直接计算。另外，这篇文章介绍一下使用迭代手算的过程。
有一点需要说明：2^k*T(n/2^k) = 2^k*T(1) := 2^k*O(1) = n*O(1) = O(n)