大佬教程收集整理的这篇文章主要介绍了Master公式，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

左程云算法与数据结构课 https://www.bilibili.com/video/BV13g41157hK?p=2&spm_id_from=pageDriver

Master 公式是用来解决递归问题时间复杂度的公式。

Master公式仅适用于子规模相等的情况

Master 公式

T(N) = a * T(N/b) + O(N^d)

1. 当 d < log_ba 时，时间复杂度为O(N^log_ba)
2. 当 d = log_ba 时，时间复杂度为O(N^d * logN)
3. 当 d > log_ba 时，时间复杂度为O(N^d)

举例

public class FindMax {
    
    public static int findMax(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        return process(arr, 0, arr.length-1);
    }

    public static int process(int[] arr, int left, int right) {
        if (left == right) {
            return arr[left];
        }
        int mid = left + ((right - left) >> 1);
        int maxLeft = process(arr, left, mid);
        int maxRight = process(arr, mid+1, right);
        return Math.max(maxLeft,maxRight);
    }
}

根据 Master 公式可知 T(N) = 2 * T(N/2) + O(N⁰)，由于 0 < log₂2，所以时间复杂度为O(N)。

大佬总结

以上是大佬教程为你收集整理的Master公式全部内容，希望文章能够帮你解决Master公式所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。