递归时间复杂度分析方法:Master 定理
编写算法时,可能因为对自己代码的复杂度的不清晰而导致错失良机,对于普通的递推或者说循环的代码,仅用简单的调和级数或者等差数列和等比数列即可分析,但是对于递归的代码,简单的递归树法并不方便,理解并记下Master定理,可以让事情变得轻松。
写此文以作笔记,如有错误,请联系博主。
Master 定理基本形式
对于一个递归式 T ( n ) = a T ( n b ) + f ( n ) T(n) = aT(\frac{n}{b}) + f(n) T(n)=aT(bn)+f(n),其中:
- a ≥ 1 a \geq 1 a≥1 和 b > 1 b > 1 b>1 是常数;
- f ( n ) f(n) f(n) 是一个给定的函数,
Master 定理帮助我们确定 T ( n ) T(n) T(n) 的渐进界。
有三种情况:
- 如果 f ( n ) = O ( n c ) f(n) = O(n^c) f(n)=O(nc),其中 c < log b a c < \log_b{a} c<logba, 那么 T ( n ) = Θ ( n log b a ) T(n) = \Theta(n^{\log_b{a}}) T(n)=Θ(nlogba)。
- 如果 f ( n ) = Θ ( n c ) f(n) = \Theta(n^c) f(n)=Θ(nc),其中 c = log b a c = \log_b{a} c=logba, 那么 T ( n ) = Θ ( n c log n ) T(n) = \Theta(n^c\log{n}) T(n)=Θ(nclogn)。
- 如果 f ( n ) = Ω ( n c ) f(n) = \Omega(n^c) f(n)=Ω(nc),其中 c > log b a c > \log_b{a} c>logba,且满足一定的平滑条件(即 a f ( n / b ) ≤ k f ( n ) af(n/b) \leq kf(n) af(n/b)≤kf(n) 对于某个常数 k < 1 k < 1 k<1 和充分大的 n n n), 那么 T ( n ) = Θ ( f ( n ) ) T(n) = \Theta(f(n)) T(n)=Θ(f(n))。
特定的例子
考虑 T ( n ) = 2 T ( n 2 ) + O ( n log n ) T(n) = 2T(\frac{n}{2}) + O(n\log{n}) T(n)=2T(2n)+O(nlogn),这里 a = 2 a = 2 a=2, b = 2 b = 2 b=2, 和 f ( n ) = n log n f(n) = n\log{n} f(n)=nlogn。显然, f ( n ) f(n) f(n) 不符合 Master 定理的标准形式中的 f ( n ) = O ( n c ) f(n) = O(n^c) f(n)=O(nc),因为增长速度比任何 n c n^c nc 形式要快。因此,直接应用标准 Master 定理的三种情况并无法获得解答。
在这种特殊情况下, T ( n ) = 2 T ( n 2 ) + n log n T(n) = 2T(\frac{n}{2}) + n\log{n} T(n)=2T(2n)+nlogn 的时间复杂度实际上是 O ( n ( log n ) 2 ) O(n(\log{n})^2) O(n(logn)2)。如有兴趣请自行查找证明过程。
相关文章:
递归时间复杂度分析方法:Master 定理
编写算法时,可能因为对自己代码的复杂度的不清晰而导致错失良机,对于普通的递推或者说循环的代码,仅用简单的调和级数或者等差数列和等比数列即可分析,但是对于递归的代码,简单的递归树法并不方便,理解并记…...
实例名不规范导致mds创建失败
概述 在部署ceph集群时,规划主机名、关闭防火墙、配置免密、关闭selinux,配置hosts文件这几步同样重要,都是初期部署一次麻烦,方便后续运维的动作。遇到过很多前期稀里糊涂部署,后续运维和配置时候各种坑。 近期遇到…...
OpenGL中的纹理过滤GL_NEAREST和GL_LINEAR
一、GL_NEAREST(最近邻插值) 1.1 原理 当需要从纹理中采样颜色时,GL_NEAREST模式会选择离采样点最近的纹理像素(通常是最接近采样点的纹理元素的中心),并直接使用该像素的颜色值作为输出。这种模式不进行任…...
vue 性能优化
data 层级不要太深 data 层级太深会增加响应式监听的计算,导致页面初次渲染时卡顿。 合理使用 v-show 和 v-if 频繁切换时,使用 v-show无需频繁切换时,使用 v-if 合理使用 computed computed 有缓存,data 不变时不会重新计算&…...
互联网大厂ssp面经(操作系统:part1)
1. 什么是进程和线程?它们之间有什么区别? a. 进程是操作系统中运行的一个程序实例。它拥有独立的地址空间和资源,可以独立执行。 b. 线程是进程内的一个执行单元,一个进程可以包含多个线程。 c. 线程共享进程的资源,…...
Android Activity 启动涉及几个进程
Zygote进程: Zygote进程在Android系统启动时被初始创建,并且初始化了虚拟机(Dalvik或ART),预加载了Android系统的核心类库。所有的Android应用进程都是通过fork()从Zygote进程派生出来的,这允许应用快速启动࿰…...
说说你对链表的理解?常见的操作有哪些?
一、是什么 链表(Linked List)是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的,由一系列结点(链表中每一个元素称为结点)组成 每个结点包括两个部分&…...
每天五分钟深度学习:逻辑回归算法的损失函数和代价函数是什么?
本文重点 前面已经学习了逻辑回归的假设函数,训练出模型的关键就是学习出参数w和b,要想学习出这两个参数,此时需要最小化逻辑回归的代价函数才可以训练出w和b。那么本节课我们将学习逻辑回归算法的代价函数是什么? 为什么不能平方差损失函数 线性回归的代价函数我们使用…...
llama-factory SFT系列教程 (二),大模型在自定义数据集 lora 训练与部署
文章目录 简介支持的模型列表2. 添加自定义数据集3. lora 微调4. 大模型 lora 权重,部署问题 参考资料 简介 文章列表: llama-factory SFT系列教程 (一),大模型 API 部署与使用llama-factory SFT系列教程 (二),大模型在自定义数…...
C语言游戏实战(11):贪吃蛇大作战(多人对战)
成果展示: 贪吃蛇(多人对战) 前言: 这款贪吃蛇大作战是一款多人游戏,玩家需要控制一条蛇在地图上移动,吞噬其他蛇或者食物来增大自己的蛇身长度和宽度。本游戏使用C语言和easyx图形库编写,旨在…...
腾讯测试岗位的面试经历与经验分享【一面、二面与三面】
腾讯两个月的实习一转眼就结束了,回想起当时面试的经过,感觉自己是跌跌撞撞就这么过了,多少有点侥幸.马上腾讯又要来校招了,对于有意愿想投腾讯测试岗位的同学们,写了一些那时候面试的经历和自己的想法,算不上经验,仅供参考吧! 一面 — —技术基础,全面…...
手机移动端网卡信息获取原理分析
有些场景我们需要获取当前手机上的网卡信息(如双卡双待、Wifi等)。本文准备研究一下这块的原理,以便更好的掌握相关技术原理。 1、底层系统接口 getifaddrs 使用 getifaddrs 接口可以达到我们的目的,该接口会返回本地所有网卡的信…...
无人新零售引领的创新浪潮
无人新零售引领的创新浪潮 在数字化时代加速演进的背景下,无人新零售作为商业领域的一股新兴力量,正以其独特的高效性和便捷性重塑着传统的购物模式,开辟了一条充满创新潜力的发展道路。 依托人脸识别、物联网等尖端技术,无人新…...
SD-WAN提升企业网络体验
在现代企业中,网络体验已成为提升工作效率与业务质量的关键因素。SD-WAN技术的出现,以其独特的优势,为企业提供了优化网络连接、加速数据传输、提升服务质量和应用访问体验,以及增强网络稳定性的解决方案。接下来,我们…...
Docker搭建Let‘s Encrypt
Let’s Encrypt是一个免费、开放和自动化的证书颁发机构(CA),它提供了一种简单、无需重复的机制来获取和更新SSL/TLS证书。Let’s Encrypt Docker镜像允许用户在容器化环境中轻松部署和使用Let’s Encrypt的服务。 主要功能包括:…...
单链表讲解
一.链表的概念以及结构 链表是一种物理结构上不连续,逻辑结构上连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表的结构与火车是类似的,一节一节的,数据就像乘客一样在车厢中一样。 与顺序表不同的…...
DFS算法系列 回溯
DFS算法系列-回溯 文章目录 DFS算法系列-回溯1. 算法介绍2. 算法应用2.1 全排列2.2 组合2.3 子集 3. 总结 1. 算法介绍 回溯算法是一种经典的递归算法,通常被用来解决排列问题、组合问题和搜索问题 基本思想 从一个初始状态开始,按一定的规则向前搜索&…...
Linux C应用编程:MQTT物联网
1 MQTT通信协议 MQTT(Message Queuing Telemetry Transport,消息队列遥测传 输)是一种基于客户端-服务端架构的消息传输协议,如今,MQTT 成为了最受欢迎的物联网协议,已广泛应用于车联网、智能家居、即时聊…...
企业常用Linux文件命令相关知识+小案例
远程连接工具无法连接VMWARE: 如果发现连接工具有时连不上,ip存在,这时候我们查看网络编辑器,更多配置,看vnet8是不是10段,nat设置是否是正确的? 软件重启一下虚机还原一下网络编辑器 查看文件…...
Istio介绍
1.什么是Istio Istio是一个开源的服务网格(Service Mesh)框架,它提供了一种简单的方式来为部署在Kubernetes等容器编排平台上的微服务应用添加网络功能。Istio的核心功能包括: 服务治理:Istio能够帮助管理服务之间的…...
代码随想录算法训练营第四十七天|leetcode115、392题
一、leetcode第392题 本题要求判断s是否为t的子序列,因此设置dp数组,dp[i][j]的含义是下标为i-1的子串与下标为j-1的子串相同字符的个数,可得递推公式是通过s[i-1]和t[j-1]是否相等区分。 具体代码如下: class Solution { publ…...
将Ubuntu18.04默认的python3.6升级到python3.8
1、查看现有的 python3 版本 python3 --version 2、安装 python3.8 sudo apt install python3.8 3、将 python3.6 和 3.8 添加到 update-alternatives sudo update-alternatives --install /usr/bin/python3 python3 /usr/bin/python3.6 1 sudo update-alternatives --insta…...
Python和Java哪个更适合后端开发?
Python和Java都是强大的后端开发语言,它们各自有鲜明的特点和适用场景。选择哪一个更适合后端开发,主要取决于具体的项目需求、团队技术栈、个人技能偏好以及长期发展考虑等因素。 下面是两者在后端开发中的优势和劣势: 「Python࿱…...
Python+pytest接口自动化之cookie绕过登录(保持登录状态)
前言 我们今天来聊聊pythonpytest接口自动化之cookie绕过登录(保持登录状态),在编写接口自动化测试用例或其他脚本的过程中,经常会遇到需要绕过用户名/密码或验证码登录,去请求接口的情况,一是因为有时验证…...
什么数据集成(Data Integration):如何将业务数据集成到云平台?
说到数据集成(Data Integration),简单地将所有数据倒入数据湖并不是解决办法。 在这篇文章中,我们将介绍如何轻松集成数据、链接不同来源的数据、将其置于合适的环境中,使其具有相关性并易于使用。 数据集成࿱…...
国外EDM邮件群发多少钱?哪个软件好?
在当今全球化市场环境下,电子邮件营销作为最有效的数字营销渠道之一,其影响力不容忽视。而高效精准的EDM(Electronic Direct Mail)邮件营销策略更是企业拓展海外市场、提升品牌知名度的关键手段。云衔科技以其创新的智能EDM邮件营…...
C语言入门算法——回文数
题目描述: 若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。 例如:给定一个十进制数 56,将 56 加 65(即把 56 从右向左读),得到 121 是一个…...
OceanBase—操作实践
文档结构 1、概念简介2、核心设计3、操作实践3.3、数据同步 官方文档:https://www.oceanbase.com/docs/oceanbase-database-cn 1、概念简介 版本分为社区版和企业版,其中企业版兼容MySQL 和Oracle数据库语法; 2、核心设计 存储层 复制层 …...
智慧用电安全管理系统
智慧用电安全管理系统 智慧用电安全管理系统是智能电网中客户侧关键的构成部分,是基本建设新型智慧城市的基本,将完成地区内各种各样用电设备的智能化系统监管,完成地区内日常生活与工作中安全性、舒服。 一、智慧用电安全管理系统介绍 …...
Rust语言入门第二篇-Cargo教程
文章目录 Rust语言入门第二篇-Cargo教程一,Cargo 是什么二,Cargo教程Cargo.toml文件src/main.rs 文件构建并运行Cargo项目 Rust语言入门第二篇-Cargo教程 本节提供对cargo命令行工具的快速了解。我们演示了它为我们生成新包的能力,它在包内编…...
wordpress跟php/重庆seo网站收录优化
如果用jquery的话: var lable_a $(li).children(a); lable_a.click(function() { lable_a.css(color, black); $(this).css(color, red); });...
网站建设第三方平台/百度网盘资源搜索入口
今天主要学了爬虫技术,爬取mp4格式,爬取豆瓣电影。一、爬虫原理 1.什么是互联网? 指的是由一堆网络设备,把一台台的计算机互联网到一起称之为互联网。 2.互联网建立的目的? 互联网建立的目的是为了数据的传递以及数据的…...
wordpress博客广告代码/网络营销项目策划方案
在JavaScript这门语言中,数据类型分为两大类:基本数据类型和复杂数据类型。基本数据类型包括Number、Boolean、String、Null、String、Symbol(ES6 新增),而复杂数据类型包括Object,而所有其他引用类型&…...
门户网站建设方案公司/兰州网络推广
本节书摘来自异步社区《Nmap渗透测试指南》一书中的第1章1.9节扫描指定段,作者 商广明,更多章节内容可以访问云栖社区“异步社区”公众号查看。 1.9 扫描指定段在Nmap中我们可以指定扫描一个C段,这个功能不需要其他额外的选项,只需要使用“-…...
怎么做一款网站/百度一下首页官网百度
问题1:.lic无法打开打开:C:\Xilinx\14.6\ISE_DS\ISE\lib\nt64 思路是这样: 将libPortability.dll重命名(加尾缀.orig,意思是original,就是保存原文件) 将libPortabilityNOSH.dll复制粘贴,并将该…...
自己建还是找代理建网站/建网站需要多少钱和什么条件
什么是一个高度平衡的二叉搜索树? 树结构中的常见用语: 节点的深度 - 从树的根节点到该节点的边数 节点的高度 - 该节点和叶子之间最长路径上的边数 树的高度 - 其根节点的高度 一个高度平衡的二叉搜索树(平衡二叉搜索树)是在插入和删除任何节点之…...