Master公式

2022-04-11 本文已影响0人爱的旋转体

形如T(N)=a*T(N/b)+O(N^d)（其中a、b、d都是常数）的递归函数，可以直接通过Master公式来确定时间复杂度。
1、 ${log_b{a}}$ > d，复杂度为O( $N^{log_b{a}}$ )；
2、 ${log_b{a}}$ < d，复杂度为O( $N^d$ )；
3、 ${log_b{a}}$ = d，复杂度为O( $N^d*{log{N}}$ )；