Java教程

算法工具--master公式

本文主要是介绍算法工具--master公式，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

master公式

T(N) = aT(N/b) + O(N^d)

image-20211030155616523

由a,b,d三个参数决定时间复杂度

  • log(b,a) > d --> O(N^log(b,a))
  • log(b,a) = d --> O(N^d*logN)
  • log(b,a) < d --> O(N^d)

例

用递归实现在整个数组中找最大值问题作为本例

public static int getMax(int[] arr,int left,int right){
    if (left == right){
        return arr[left];//直接返回,O(1)
    }
    int mid = left+(right-left)/2;//求中间值O(1)
    int maxLeft = getMax(arr, left, mid);//子问题的规模是N/2
    int maxRight = getMax(arr, mid+1, right);//子问题的规模是N/2
    return Math.max(maxLeft,maxRight);//比大小O(1)
}

由于子问题的规模都是等量的N/2,就可以使用master公式,调用两次那么a就是2,其余操作的时间复杂度都是O(1),那么本题的master公式就是T(N) = 2*T(N/2)+O(1)

这篇关于算法工具--master公式的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航