此笔记来源于左神算法,只用做笔记使用,已注明来源。
此事件复杂度只适用于递归算法,并且递归过程中要求数据规模大体相同
T ( N ) = a ∗ T ( N b ) + O ( N d ) T(N)=a*Tleft(frac{N}{b}right)+O(N^d) T(N)=a∗T(bN)+O(Nd)
1 当 log b a > d log_ba>d logba>d 复杂度为 O ( N log b a ) Oleft(N^{log_ba}right) O(Nlogba)2 当 log b a < d log_ba<d logba<d 复杂度为 O ( N d ) Oleft(N^dright) O(Nd)3 当 log b a = d log_ba=d logba=d 复杂度为 O ( N d × log N ) Oleft(N^dtimes{log{N}}right) O(Nd×logN)a为将数据分成几块,b为每块数据占用总数据的数据量, O ( N d ) O(N^d) O(Nd)为每迭代的时间复杂度,然后计算d的值