Master主定理求递归算法的时间复杂度

2023-12-27 13:27:12

Master主定理的递归关系式

T(n) = aT(n/b) + O(n^d)其中a,b >= 1并且是常数。

  • a是递归的子问题的数量

  • n / b是每个子问题的规模

  • f（n）为递归进行计算工作

现在来看一个例子，归并排序

  • 总共有n个元素

  • 每次把一个数组拆成两个小数组(a=2)，每个大小约为原来的一半(n / 2, 故b=2)

  • 我们会对当前得到的，已经被排序过的两个n/2的数组拿回来，所以要对n/2 * 2也就是n个元素进行处理

于是我们可以轻松的得到归并排序的关系式：

T(n) = 2T(n / 2) + n

如何使用主定理

  • 使用上面的公式求出a，b，d。然后套用下面的公式直接求出时间复杂度。

回到上面的归并排序：我们带入公式可以得到归并排序的时间复杂度为O(n*logn)

文章来源:https://blog.csdn.net/qq_61039408/article/details/135233760
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。