当前位置:网站首页>Master公式。(用于计算递归的时间复杂度。)
Master公式。(用于计算递归的时间复杂度。)
2022-07-07 10:33:00 【Kinght_123】
一、Mster公式
前提条件:
- 递归的子问题的规模必须是相同的。
下面让我来解释一下,这个公式具体的含义。
首先a是一个递归问题的子问题的规模的调用次数,d是子问题的数目,后面的N的d次方就是除了递归子问题的调用,其他问题规模的时间复杂度。
举个例子:
def func(arr, l, r): # 再arr数组中找到最大的数值
if l == r:
return arr[l]
mid = l + ((r - l) >> 1)
l_max = func(arr, l, mid)
r_max = func(arr, mid + 1, r)
return max(l_max, r_max)
比如上面的代码就是一个简单的递归。
那么的它的T(N) = 2 * T(N / 2) + O(1)
因为每次调用主函数,需要调用两次规模相同的子问题的函数,所以为2 * T(N / 2),又因为它除了调用子问题的函数,其他的时间复杂度为O(1).所以这就是这个递归的Master公式。
二、计算时间复杂度
按照这个公式和我们上面的代码,时间复杂度应该为O(N)
边栏推荐
- 普乐蛙小型5d电影设备|5d电影动感电影体验馆|VR景区影院设备
- Cryptography series: detailed explanation of online certificate status protocol OCSP
- [pytorch practice] image description -- let neural network read pictures and tell stories
- 2022聚合工艺考试题模拟考试题库及在线模拟考试
- Inverted index of ES underlying principle
- gcc 编译报错
- Financial data acquisition (III) when a crawler encounters a web page that needs to scroll with the mouse wheel to refresh the data (nanny level tutorial)
- [疑难杂症]pip运行突然出现ModuleNotFoundError: No module named ‘pip‘
- Cenos openssh upgrade to version 8.4
- Idea 2021 Chinese garbled code
猜你喜欢
RHSA first day operation
什么是ESP/MSR 分区,如何建立ESP/MSR 分区
[pytorch practice] write poetry with RNN
[爬虫]使用selenium时,躲避脚本检测
静态Vxlan 配置
Aike AI frontier promotion (7.7)
Financial data acquisition (III) when a crawler encounters a web page that needs to scroll with the mouse wheel to refresh the data (nanny level tutorial)
Tutorial on principles and applications of database system (009) -- conceptual model and data model
leetcode刷题:二叉树22(二叉搜索树的最小绝对差)
JS to convert array to tree data
随机推荐
Multi row and multi column flex layout
Several ways to clear floating
Tutorial on principles and applications of database system (010) -- exercises of conceptual model and data model
Is it safe to open an account in Ping An Securities mobile bank?
sql-lab (54-65)
Static comprehensive experiment
广州市召开安全生产工作会议
leetcode刷题:二叉树19(合并二叉树)
Realize all, race, allsettled and any of the simple version of promise by yourself
Session
【统计学习方法】学习笔记——提升方法
2022危险化学品生产单位安全生产管理人员考题及在线模拟考试
ps链接图层的使用方法和快捷键,ps图层链接怎么做的
About web content security policy directive some test cases specified through meta elements
EPP+DIS学习之路(2)——Blink!闪烁!
Attack and defense world - PWN learning notes
[爬虫]使用selenium时,躲避脚本检测
Solutions to cross domain problems
Static routing assignment of network reachable and telent connections
(待会删)yyds,付费搞来的学术资源,请低调使用!