使用master公式分析递归的时间复杂度

发表于 分类于 阅读次数： 本文字数： 531 阅读时长 ≈ 1 分钟

适用场景

所有子问题规模相同的递归才能用master公式

公式介绍

T(n) = a * T(n/b) + O(n^c), 其中a, b, c都是常数, a为执行了几次相同规模的子问题，b为子问题的规模，O(n^c)为递归问题外的其他时间复杂度

  1. 如果log(b, a) < c 复杂度为O(n^c)
  2. 如果log(b, a) > c 复杂度为O(n^log(b, a))
  3. 如果log(b, a) == c 复杂度为O(n^c * log n)

补充

T(n) = 2*T(n/2) + O(n*log n)的时间复杂度为O(n* ((log n)的平方))

实例分析

1
2
3
4
5
6
7
int getMax(vector<int>& nums, int l, int r) {
    if (l == r) return nums[l];
    int mid = (l + r) / 2;
    int lmax = getMax(nums, l, mid);
    int rmax = getMax(nums, mid + 1, r);
    return max(lmax, rmax);
}

根据master公式，可得T(n) = 2*(n/2) + O(1)，进而a = 2, b = 2, c = 0，从而log(2, 2) > c，由此时间复杂度为O(n)

感谢

本文整理自左神的 算法讲解020【必备】递归和master公式