master 公式
master公式
T(N) = a*T(N/b) + O(Nd)
N:样本量 T:时间复杂度 a:样本量发生的次数 b:将样本量进行分治 c:执行子过程之外其余过程的时间复杂度
用途:计算递归算法的时间复杂度
快速计算
- logba > d -> 复杂度为O(Nlogba)
- logba = d -> 复杂度为O(Nd * logN)
- logba < d -> 复杂度为O(Nd)
适用范围 递归调用使,划分的子过程规模一样, 奇数问题:递归不看常数
任何递归行为都可以变成非递归 递归的本质是 压栈
- 原文作者:浮华生
- 原文链接:https://www.ahianzhang.com/post/algorithm-master-formula/
- 版权声明:本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可,非商业转载请注明出处(作者,原文链接),商业转载请联系作者获得授权。