数据结构和算法分析之递归行为时间复杂度的估算

本文主要是介绍数据结构和算法分析之递归行为时间复杂度的估算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

master公式：T(N) = aT(N/b) + O(N^d)*

递归行为的规模|样本数量 T(N)：递归的时间复杂度
N/b：递归后子过程的规模
a:子过程的个数
除去递归之外的时间复杂度为O(N^d)

• log(b,a) > d -> 复杂度为O(N^log(b,a))
• log(b,a) = d -> 复杂度为O(N^d * logN)
• log(b,a) < d -> 复杂度为O(N^d)

eg：快排为T(N)=2T(N/2)+O(N),复杂度为O(N*log(N))

这篇关于数据结构和算法分析之递归行为时间复杂度的估算的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---