当前位置: 首页 > news >正文

主定理(简化版)

主定理(Master Theorem)是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系,通常采用分治策略解决问题的情况。

假设我们有一个递归算法,它将问题分解成 a a a 个子问题,每个子问题的规模是原问题的 1 b \frac{1}{b} b1,解决每个子问题的代价是 f ( n ) f(n) f(n),而将子问题的解合并成原问题的解的代价是 g ( n ) g(n) g(n)。那么该递归算法的时间复杂度可以表示为:
T ( n ) = a ⋅ T ( n b ) + f ( n ) T(n)=a·T(\frac{n}{b})+f(n) T(n)=aT(bn)+f(n)
其中, a ≥ 1 , b > 1 a ≥ 1,b > 1 a1b>1 是常数, f ( n ) f(n) f(n) 是解决一个规模为 n n n 的问题所需的工作量, g ( n ) g(n) g(n) 是合并子问题的解的工作量。

主定理的三种情况:

  1. I F IF IF f ( n ) = O ( n l o g b ( a − ε ) ) f(n) = O(n^ {log_b(a - ε)}) f(n)=O(nlogb(aε)),and ε > 0 ε > 0 ε>0,Then T ( n ) = Θ ( n l o g b ( a ) ) T(n) = Θ(n^{log_b(a)}) T(n)=Θ(nlogb(a))
  2. I F IF IF f ( n ) = Θ ( n l o g b ( a ) ⋅ l o g k n ) f(n) = Θ(n^{log_b(a)} ·log^k n) f(n)=Θ(nlogb(a)logkn),and k ≥ 0 k ≥ 0 k0,Then T ( n ) = Θ ( n l o g b ( a ) ⋅ l o g k + 1 n ) T(n) = Θ(n^{log_b(a)} · log^{k+1} n) T(n)=Θ(nlogb(a)logk+1n)
  3. I F IF IF f ( n ) = Ω ( n l o g b ( a + ε ) ) f(n) = Ω(n^{log_b(a + ε)}) f(n)=Ω(nlogb(a+ε)),and ε > 0 ε > 0 ε>0 a ⋅ f ( n b ) ≤ c ⋅ f ( n ) a · f(\frac{n}{b}) ≤ c · f(n) af(bn)cf(n) 对于某个常数 c < 1 c < 1 c<1 和所有足够大的 n n n 成立,Then T ( n ) = Θ ( f ( n ) ) T(n) = Θ(f(n)) T(n)=Θ(f(n))

情况一:

T ( n ) = 4 T ( n 2 ) + n T(n)=4T(\frac{n}{2})+n T(n)=4T(2n)+n

其中 a = 4 ≥ 1 , b = 2 > 1 , f ( n ) = n , l o g 2 4 = 2 > 1 a = 4\ge1,b = 2>1,f(n) = n,log_{2}4=2>1 a=41b=2>1f(n)=nlog24=2>1

根据主定理的第一种情况: f ( n ) = O ( n l o g b ( a − ε ) ) f(n) = O(n^ {log_b(a - ε)}) f(n)=O(nlogb(aε))

可得 n = O ( n l o g 2 ​ 4 − ε ) = O ( n 2 ) n=O(n^{log_{2}​4−ε})=O(n^{2}) n=O(nlog2​4ε)=O(n2)

∴ T ( n ) = Θ ( n 2 ) \therefore T(n)=Θ(n^{2}) T(n)=Θ(n2)


情况二:

T ( n ) = 4 T ( n 2 ) + n 2 T(n)=4T(\frac{n}{2})+n^{2} T(n)=4T(2n)+n2

其中 a = 4 ≥ 1 , b = 2 > 1 , f ( n ) = n 2 , l o g 2 4 = 2 a = 4\ge1,b = 2>1,f(n) = n^{2},log_{2}4=2 a=41b=2>1f(n)=n2log24=2

根据主定理的第二种情况: f ( n ) = O ( n l o g b ( a ) l o g k n ) f(n) = O(n^ {log_b(a )}log^{k}n) f(n)=O(nlogb(a)logkn)

可得 n 2 = Θ ( n l o g 2 ​ 4 l o g 0 n ) = Θ ( n 2 ) n^{2}=Θ(n^{log_{2}​4}log^{0}n)=Θ(n^{2}) n2=Θ(nlog2​4log0n)=Θ(n2)

∴ T ( n ) = Θ ( n 2 l o g n ) \therefore T(n)=Θ(n^{2}logn) T(n)=Θ(n2logn)


情况三:

T ( n ) = 2 T ( n 2 ) + n 2 T(n)=2T(\frac{n}{2})+n^{2} T(n)=2T(2n)+n2

其中 a = 2 ≥ 1 , b = 2 > 1 , f ( n ) = n 2 , l o g 2 2 = 1 < 2 a = 2\ge1,b = 2>1,f(n) = n^{2},log_{2}2=1<2 a=21b=2>1f(n)=n2log22=1<2

根据主定理的第三种情况: f ( n ) = Ω ( n l o g b ( a ) + ε ) f(n) = Ω(n^ {log_b(a )+ε }) f(n)=Ω(nlogb(a)+ε)

可得 n 2 = Ω ( n l o g 2 ​ 2 + ε ) = Ω ( n 1 + ε ) n^{2}=Ω(n^{log_{2}​2+ε})=Ω(n^{1+ε}) n2=Ω(nlog2​2+ε)=Ω(n1+ε)

但我们还需要检查是否满足 a ⋅ f ( n b ) ≤ c ⋅ f ( n ) a · f(\frac{n}{b}) ≤ c · f(n) af(bn)cf(n) 的条件:

2 ⋅ ( n / 2 ) 2 ≤ c ⋅ n 2 n 2 / 2 ≤ c ⋅ n 2 1 / 2 ≤ c 2·(n/2)^{2}≤c·n^{2}\\ n^{2}/{2}≤c·n^{2}\\ 1/2≤c 2(n/2)2cn2n2/2cn21/2c

对于任何小于 1/2 的常数 c c c,上述不等式都成立

∴ T ( n ) = Θ ( n 2 ) \therefore T(n)=Θ(n^{2}) T(n)=Θ(n2)


相关文章:

主定理(简化版)

主定理&#xff08;Master Theorem&#xff09;是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系&#xff0c;通常采用分治策略解决问题的情况。 假设我们有一个递归算法&#xff0c;它将问题分解成 a a a 个子问题&#xff0c;每个子问题的规模…...

HTTP1.0和HTTP2.0的区别

相同点&#xff1a;所有的HTTP请求都要基于TCP连接。 HTTP1.0&#xff1a;每次发送请求时建立一个TCP连接&#xff0c;得到响应后&#xff0c;释放TCP连接。 HTP1.1&#xff1a;**相比于1.0&#xff0c;引入了Keep live&#xff0c;客户端得到响应后&#xff0c;不会立刻释放T…...

ARM资源记录《AI嵌入式系统:算法优化与实现》第八章(暂时用不到)

1.CMSIS的代码 书里给的5&#xff0c;https://github.com/ARM-software/CMSIS_5 现在有6了&#xff0c;https://github.com/ARM-software/CMSIS_6 这是官网的书&#xff0c;介绍cmsis函数的https://arm-software.github.io/CMSIS_5/Core/html/index.html 2.CMSIS介绍 Cort…...

微信小程序2

一&#xff0c;视图层 1.什么视图层 框架的视图层由 WXML 与 WXSS 编写&#xff0c;由组件来进行展示。 将逻辑层的数据反映成视图&#xff0c;同时将视图层的事件发送给逻辑层。 WXML(WeiXin Markup language) 用于描述页面的结构。 WXS(WeiXin Script) 是小程序的一套脚本语…...

G.711语音编解码器详解

语音编解码利用人听觉上的冗余对语音信息进行压缩从而达到节省带宽的目的。值得注意的是,本文说的是语音编解码器,也就Speech codec,而常用的还有另一种编解码器称作音频编解码器,英文是Audio codec,它们的区别如下。 以前在学校的时候研究了很多VoIP的编解码器从G.723到A…...

蓝桥杯每日一题2023.10.17

迷宫 - 蓝桥云课 (lanqiao.cn) 题目描述 样例&#xff1a; 01010101001011001001010110010110100100001000101010 00001000100000101010010000100000001001100110100101 01111011010010001000001101001011100011000000010000 0100000000101010001101000010100000101010101100…...

16.SpringBoot前后端分离项目之简要配置一

SpringBoot前后端分离项目之简要配置一 前面对后端所需操作及前端页面进行了了解及操作&#xff0c;这一节开始前后端分离之简要配置 为什么要前后端分离 为了更低成本、更高效率的开发模式。 前端有一个独立的服务器。 后端有一个独立的服务器。两个服务器之间实时数据交换…...

Probability Calibration概率校准大比拼:性能、应用场景和可视化对比总结

在机器学习中,概率校准(Probability Calibration)是一个重要的概念。简单来说,概率校准就是将分类器输出的原始预测概率转换为更准确、更可靠的概率值。这样做的目的是为了让模型的预测结果更接近实际情况,从而提高模型在特定应用场景中的可用性。 在Python的Scikit-Lear…...

PHP 球鞋在线商城系统mysql数据库web结构apache计算机软件工程网页wamp计算机毕业设计

一、源码特点 PHP球鞋在线商城系统是一套完善的web设计系统&#xff0c;对理解php编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。 php球鞋在线商城系统 代码 https://download.csdn.net/download/qq_41221322/8843725…...

使用Apache和内网穿透实现私有服务公网远程访问——“cpolar内网穿透”

文章目录 前言1.Apache服务安装配置1.1 进入官网下载安装包1.2 Apache服务配置 2.安装cpolar内网穿透2.1 注册cpolar账号2.2 下载cpolar客户端 3. 获取远程桌面公网地址3.1 登录cpolar web ui管理界面3.2 创建公网地址 4. 固定公网地址 前言 Apache作为全球使用较高的Web服务器…...

PreparedStatement

使用参数化查询&#xff1a;使用预编译的语句和参数化查询来执行SQL语句&#xff0c;而不是将用户输入直接嵌入到SQL语句中。这将帮助防止恶意输入注入SQL语句。...

CSS3 新增属性-边框圆角-文字阴影-盒子阴影

边框圆角 CSS 边框圆角可以通过 border-radius 属性来实现。该属性用于设置元素的圆角大小&#xff0c;支持四个值分别表示上左、上右、下右和下左四个角的圆角半径大小&#xff0c;也可以使用两个值分别表示上下和左右两个方向的圆角大小&#xff0c;甚至可以只使用一个值来…...

制作.a静态库 (封盒)

//云库房间 1.GitHub上创建开源框架项目须包含文件&#xff1a; LICENSE:开源许可证&#xff1b;README.md:仓库说明文件&#xff1b;开源项目&#xff1b;(登录GitHub官网) 2. 云仓储库构建成功(此时云库中没有内容三方框架)&#xff01;&#xff01;&#xff01; 3. 4.5. //…...

一台服务器,一个新世界

我如何看待服务器 当我拥有一台服务器&#xff0c;我看到的不仅仅是一块硬件&#xff0c;而是一扇打开未来的大门&#xff0c;一个我可以将自己的愿景和创意投射到其中的平台。这台服务器是我的工具&#xff0c;我的画布&#xff0c;我将在其中铸造我的数字梦想。 第一步我要…...

keep-alive 是 Vue 的一个内置组件,用于缓存其他组件的实例,以避免重复渲染和销毁,它可以在需要频繁切换的组件之间提供性能优化

目录 keep-alive 使用 keep-alive 的示例代码&#xff1a; 手动清除组件缓存的示例代码&#xff1a; keep-alive 组件有以下几个优点&#xff1a; keep-alive 的原理&#xff1a; 使用 keep-alive 组件&#xff0c;你可以包裹需要缓存的组件&#xff0c;然后这些组件在切…...

(八)Python类和对象

Python 语言在设计之初&#xff0c;就定位为一门面向对象的编程语言&#xff0c;“Python 中一切皆对象”就是对 Python 这门编程语言的完美诠释。 类和对象是 Python 的重要特征&#xff0c;相比其它面向对象语言&#xff0c;Python 很容易就可以创建出一个类和对象。同时&am…...

黑客利用人工智能窃取医疗数据的 7 种方式

人工智能被描述为医疗保健行业的一把双刃剑。基于人工智能的系统可以分析大量数据并在早期和可治疗的阶段检测疾病&#xff0c;它们可以比任何人类更快地诊断症状&#xff0c;并且人工智能正在帮助药物开发&#xff0c;使新的救命药物得以识别并将其推向市场速度更快且成本显着…...

OJ第四篇

文章目录 链表分割环形链表有效的括号 链表分割 链接: 链表分割 虽然这个题牛客网中只有C,但是无所谓&#xff0c;我们只要知道C是兼容C的就可以了 至于说这个题的思路&#xff0c;我们就弄两个链表&#xff0c;把小于x的结点放到一个链表中&#xff0c;剩下的放到另一个链表…...

L2-022 重排链表

给定一个单链表 L1​→L2​→⋯→Ln−1​→Ln​&#xff0c;请编写程序将链表重新排列为 Ln​→L1​→Ln−1​→L2​→⋯。例如&#xff1a;给定L为1→2→3→4→5→6&#xff0c;则输出应该为6→1→5→2→4→3。 输入格式&#xff1a; 每个输入包含1个测试用例。每个测试用例…...

css 特别样式记录

一、 这段代码神奇的地方在于&#xff0c; 本来容器的宽度只有1200px&#xff0c;如果不给img赋予宽度100%&#xff0c;那么图片 会超出盒子&#xff0c;如果给了img赋予了宽度100%&#xff0c;多个图片会根据自己图片大小的比例&#xff0c;去分完那1200px&#xff0c;如图二。…...

Umi-OCR技术解析:离线文字识别的创新实践与全场景应用

Umi-OCR技术解析&#xff1a;离线文字识别的创新实践与全场景应用 【免费下载链接】Umi-OCR OCR software, free and offline. 开源、免费的离线OCR软件。支持截屏/批量导入图片&#xff0c;PDF文档识别&#xff0c;排除水印/页眉页脚&#xff0c;扫描/生成二维码。内置多国语言…...

如何用11款开源字体解锁创作可能?宝藏资源轻松上手游戏文字设计

如何用11款开源字体解锁创作可能&#xff1f;宝藏资源轻松上手游戏文字设计 【免费下载链接】HoYo-Glyphs Constructed scripts by HoYoverse 米哈游的架空文字 项目地址: https://gitcode.com/gh_mirrors/ho/HoYo-Glyphs 你是否曾在创作同人作品时&#xff0c;苦于找不…...

网站纠错页面对 SEO 有什么作用_网站图片和视频优化对 SEO 有什么技巧

网站纠错页面对 SEO 有什么作用 在网站管理和搜索引擎优化&#xff08;SEO&#xff09;方面&#xff0c;纠错页面的作用常常被忽视。网站纠错页面实际上对 SEO 有着重要的影响。当用户访问一个网站时&#xff0c;如果遇到 404 错误&#xff08;页面未找到&#xff09;或其他错…...

别盲目冲网安!普通本科转行 5 年月薪 2 万 +,掏心窝子真话

别盲目冲网安&#xff01;普通本科转行5年&#xff0c;月薪2万的真心话 网安行业确实火&#xff0c;但真话难听&#xff1a;这行超卷&#xff0c;缺的是能干活的实战派&#xff0c;不是凑数的小白。 我普通本科出身&#xff0c;转行网安5年&#xff0c;如今月薪2万&#xff0…...

GLM-4.1V-9B-Base实战教程:批量图片队列处理与异步结果回调机制实现

GLM-4.1V-9B-Base实战教程&#xff1a;批量图片队列处理与异步结果回调机制实现 1. 引言 在实际业务场景中&#xff0c;我们经常需要处理大量图片的分析任务。GLM-4.1V-9B-Base作为一款强大的视觉多模态理解模型&#xff0c;虽然提供了便捷的Web界面&#xff0c;但面对批量图…...

bert-base-chinese新手必看:完形填空与语义相似度功能实测教程

bert-base-chinese新手必看&#xff1a;完形填空与语义相似度功能实测教程 1. 快速了解bert-base-chinese bert-base-chinese是Google发布的经典中文预训练模型&#xff0c;作为NLP领域的基础模型&#xff0c;它已经成为中文自然语言处理任务的标准选择之一。这个模型特别适合…...

华为eNSP实战:手把手教你用单臂路由打通不同VLAN,附排错命令清单

华为eNSP单臂路由实战&#xff1a;跨VLAN通信配置与深度排错指南 当企业网络规模扩大时&#xff0c;VLAN隔离是保障安全性和广播域控制的必要手段。但实际业务中&#xff0c;不同部门间的数据交互需求常常需要跨越VLAN边界。在华为认证体系HCIA和HCIP的实验环境中&#xff0c;单…...

测试流程图显示

一、原理解析 / 概念介绍 1.1 自动化序列化流水线 hive_generator 处于开发链路的“后台”&#xff0c;负责将 Dart 对象转换为 Hive 识别的二进制流编码逻辑。 #mermaid-svg-bbx9YEu5DFSBhCuG{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;…...

word简历模板(含范文),免费下载

word简历模板导言 在竞争激烈的求职市场中&#xff0c;一份专业、个性化的简历是叩开理想企业大门的关键。简历不仅是个人经历的罗列&#xff0c;更是能力、潜力与职业规划的集中体现。然而&#xff0c;许多求职者因缺乏经验或模板参考&#xff0c;难以突出自身优势&#xff0…...

TI SAR ADC模型(Matlab) 包含各类非理想因素,时钟偏差,增益偏差

TI SAR ADC模型&#xff08;Matlab&#xff09; 包含各类非理想因素&#xff0c;时钟偏差&#xff0c;增益偏差&#xff0c;失调偏差 模型参数均可自由设置直接上干货吧&#xff0c;今天聊聊怎么用Matlab折腾带非理想特性的SAR ADC模型。玩过ADC的都知道&#xff0c;现实中的转…...