Master Theorem
前言
在介绍主定理之前,需要了解一下关于表示时间复杂度的几种形式。
主定理
主定理主要解决递归式的时间复杂度计算。但并不能解决所有的递归式。主要适用如下递归式:
三种 case
简化版本
总结
计算递归时间复杂度的话,一般两种方法,画递归树手算和用主定理,具体情况具体分析。
最后更新于
在介绍主定理之前,需要了解一下关于表示时间复杂度的几种形式。
主定理主要解决递归式的时间复杂度计算。但并不能解决所有的递归式。主要适用如下递归式:
三种 case
简化版本
计算递归时间复杂度的话,一般两种方法,画递归树手算和用主定理,具体情况具体分析。
最后更新于
表示最坏时间复杂度,为上界。
表示最优时间复杂度,为下界。
表示确界,当上界和下届相同时,可以用这个来表示时间复杂度。
是问题规模。
为递归的子问题。
为每个子问题的规模。
为递归以外的计算量。
主定理的结果主要跟 有关。
当 其中 (相当于 ),则有 。
当 ,则有。
当 其中 (相当于),则有
如果 (其中 ),则有