algorithm - 确定分治算法的适当递归函数

Question

很长一段时间以来，我一直试图了解复发的本质。我特别好奇如何产生用于递归的函数 (T(n))。例如在归并排序中，时间复杂度可以说是 T(n) = 2T(n/2) + cn。我看不到这与合并排序中的递归调用之间的联系。

我理解大师理论的概念。a 应该是递归调用的数量，b 应该是每次调用中输入缩小的因子，d 是在递归算法之外完成的工作。我只是不明白合并排序中的任何工作是如何在递归算法之外完成的，因为算法完成的所有工作都是由递归调用中的一个以某种方式产生的。

slice1 = Arrays.copyOfRange(u_arr, 0, half); // this takes O(n) time, better method?
slice2 = Arrays.copyOfRange(u_arr, half, u_arr.length);
        arr1 = this.mergesort(slice1);
        arr2 = this.mergesort(slice2);
        return this.merge(arr1, arr2);
    }

排除基本情况、一些初始化和合并函数，该算法完成的任何工作如何在递归调用之外完成？并且鉴于可以确定递归调用之外的运行时间，那么递归本质上是否只是一个模板函数，用于插入分治算法的特征，例如 T(n/b) + O(n^d)？给定适当的 a、b 和 d。

标签： algorithmrecurrencemaster-theorem