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

Unit1_1:分治问题之时间复杂度求解

文章目录

  • 背景
  • 递归树法
    • 案例一
    • 案例二
    • 局限性
  • 代入法/替代法
  • 主方法(重点)

背景

当碰到形如 T ( n ) = a T ( ⌈ n b ⌉ ) + O ( n d ) T(n)=aT(\lceil \frac{n}{b} \rceil)+O(n^d) T(n)=aT(⌈bn⌉)+O(nd)的递推式,本质上就是将问题转化为规模更小的子问题求解,此时有三种思路。

递归树法

案例一

T ( n ) = { 2 T ( n 2 ) + n i f n > 1 1 i f n = 1 T(n)=\left\{ \begin{array}{ll} 2T(\frac{n}{2})+n & if \space n>1 \\ 1 & if \space n=1 \nonumber \end{array} \right. T(n)={2T(2n)+n1if n>1if n=1
可以利用递归树:
在这里插入图片描述
画出树,高满足 2 h = n 2^h=n 2h=n,因此 h = l o g 2 n h=log_{2}n h=log2n,而叶子共有n个,因此总的时间复杂度 T ( n ) = n l o g n T(n)=nlogn T(n)=nlogn

案例二

T ( n ) = { 3 T ( n 4 ) + n 2 i f n > 1 1 i f n = 1 T(n)=\left\{ \begin{array}{ll} 3T(\frac{n}{4})+n^2 & if \space n>1 \\ 1 & if \space n=1 \nonumber \end{array} \right. T(n)={3T(4n)+n21if n>1if n=1
在这里插入图片描述
每层个数即 3 h 3^h 3h个。最后一层高度 h = l o g 4 n h=log_4n h=log4n,再利用对数技巧代入,即可求出叶子的个数,而时间复杂度为:
在这里插入图片描述
等比数列求解

局限性

T ( n ) = { T ( n 3 ) + T ( 2 n 3 ) + n i f n > 2 1 i f n = 1 , 2 T(n)=\left\{ \begin{array}{ll} T(\frac{n}{3})+ T(\frac{2n}{3})+n & if \space n>2 \\ 1 & if \space n=1,2 \nonumber \end{array} \right. T(n)={T(3n)+T(32n)+n1if n>2if n=1,2
在这里插入图片描述
此时树的高度不一致,无法计算

代入法/替代法

此法先假设时间复杂度,再去验证假设成立。因此最难之处在于怎么假设,用处不大

主方法(重点)

T ( n ) = a T ( ⌈ n b ⌉ ) + O ( n d ) T(n)=aT(\lceil \frac{n}{b} \rceil)+O(n^d) T(n)=aT(⌈bn⌉)+O(nd)的时间复杂度如下:

T ( n ) = { O ( n d ) d > log ⁡ b a O ( n d l o g n ) d = log ⁡ b a O ( n log ⁡ b a ) d < log ⁡ b a T(n)=\left\{ \begin{array}{ll} O(n^d) & d>\log_{b}a \\\\ O(n^{d}logn) & d=\log_{b}a \\\\ O(n^{\log_{b}a}) & d<\log_{b}a \nonumber \end{array} \right. T(n)= O(nd)O(ndlogn)O(nlogba)d>logbad=logbad<logba

以后碰到这种递推分治式子代入公式即可

相关文章:

Unit1_1:分治问题之时间复杂度求解

文章目录 背景递归树法案例一案例二局限性 代入法/替代法主方法&#xff08;重点&#xff09; 背景 当碰到形如 T ( n ) a T ( ⌈ n b ⌉ ) O ( n d ) T(n)aT(\lceil \frac{n}{b} \rceil)O(n^d) T(n)aT(⌈bn​⌉)O(nd)的递推式&#xff0c;本质上就是将问题转化为规模更小的…...

React hooks的闭包陷阱

react hooks 陷阱 hooks必须放在函数顶层&#xff0c; 不能在条件分支和方法内 1、useState陷阱 异步陷阱 function Index() {const [count, setCount] useState(0)function add(){setCount( count 1 )console.log(count); // 0}return (<div><span>{count}…...

20.3 OpenSSL 对称AES加解密算法

AES算法是一种对称加密算法&#xff0c;全称为高级加密标准&#xff08;Advanced Encryption Standard&#xff09;。它是一种分组密码&#xff0c;以128比特为一个分组进行加密&#xff0c;其密钥长度可以是128比特、192比特或256比特&#xff0c;因此可以提供不同等级的安全性…...

一文详解防御DDoS攻击的几大有效办法

伴随互联网的飞速发展&#xff0c;网络安全问题变得越来越突出&#xff0c;其中最常见的就是DDoS攻击&#xff0c;也就是分布式拒绝服务攻击。DDoS攻击者利用计算机或其他设备的协作&#xff0c;以发送大量请求的方式导致目标超负荷&#xff0c;导致不能正常运转或“宕机”。以…...

Python二级 每周练习题24

练习一: 体重比较器 要求: 请编程实现如下功能: (1)程序开始运行时&#xff0c;提醒用户输入三个人的名字和体重 (可以分开输入&#xff0c;每次输入名字或者体重) (2) 程序自动比较&#xff0c;找出最重的一个人的名字和体重输出 的格式不限&#xff0c;但是要有最重人的姓名…...

MySQL - Buffer Pool

Buffer Pool 主要用于缓存数据库表的数据页&#xff0c;以提高数据库的读取性能&#xff1a; 缓存数据页&#xff1a;Buffer Pool 是 MySQL 中用于缓存数据页的内存区域。数据页通常包含数据库表的数据&#xff0c;如行记录等。当查询或读取数据时&#xff0c;MySQL会首先查看…...

c++ 拆分函数返回值和参数类型

在c中&#xff0c;函数参数类型和返回值类型通常是一个比较明确的信息&#xff0c;好像确实无需在这个上面费周折。然而&#xff0c;硬编码数据类型会让代码复用性下降&#xff0c;如果能够通过某种方式自动获取函数参数和返回值类型&#xff0c;对于代码的可复用性&#xff0c…...

Ubuntu 23.10安装TeXlive并安装CTEX中文支持

连接上互联网&#xff0c;打开SHELL命令行界面&#xff0c; 1. sudo apt install texlive texstudio texlive-lang-chinese 就可以安装好了。texlive-lang-chinese 是TEXLIVE对CTEX中文的支持。 2. Tex源文件必须采用UTF-8编码格式&#xff0c;编译器采用xelatex。这样对中文…...

SpringBoot中CommandLineRunner详解(含源码)

文章目录 前言实例导入库application.yamlRunnerSpringBootCommandLineRunnerApplication执行结果 先后顺序示例OrderRunner1OrderRunner2执行结果 通常用法加载初始化数据示例 启动后打印应用信息示例 启动异步任务示例 接口健康检查示例 外部服务调用示例 参数校验示例 动态设…...

通信基础(一):数据传输基础

一、波特率与比特率关系 比特率(信息传输速率、信息速率):指单位时间内在信道上传 送的数据量(即比特数),单位为比特每秒 (bit/s), 简记为b/s或bps。 波特率与比特率有如下换算关系&#xff1a; bitbaud *log 2(N) 其中&#xff0c; N是码元总类数。 特别注意&#xff…...

故障诊断模型 | Maltab实现BiLSTM双向长短期记忆神经网络故障诊断

文章目录 效果一览文章概述模型描述源码设计参考资料效果一览 文章概述 故障诊断模型 | Maltab实现BiLSTM双向长短期记忆神经网络故障诊断 模型描述 利用各种检查和测试方法,发现系统和设备是否存在故障的过程是故障检测;而进一步确定故障所在大致部位的过程是故障定位。故障…...

物联网和互联网医院小程序:如何实现医疗设备的远程监测和管理?

物联网&#xff08;IoT&#xff09;技术的发展为医疗设备的远程监测和管理提供了巨大的机会。结合互联网医院小程序&#xff0c;我们可以实现对医疗设备的远程访问、监控和管理&#xff0c;从而提高医疗服务的质量和效率。本文将介绍如何实现医疗设备的远程监测和管理&#xff…...

sharepoint2016-2019升级到sharepoint订阅版

一、升级前准备&#xff1a; 要建立新的sharepoint订阅版环境&#xff0c;需求如下&#xff1a; 1.单服务器硬件需求CPU 4核&#xff0c;内存24G以上&#xff0c;硬盘300G&#xff08;根据要迁移的数量来扩容大小等&#xff09;&#xff1b; 2.操作系统需要windows server 20…...

CTFHub | MySQL流量、Redis流量、MongoDB流量的WriteUp

文章目录 MySQL流量题目题解 Redis流量题目题解 MongoDB流量题目题解 数据库类流量题需要用到Wireshark截取数据包&#xff0c;然后进行分析。 WireShark是非常流行的网络封包分析工具&#xff0c;可以截取各种网络数据包&#xff0c;并显示数据包详细信息。常用于开发测试过程…...

NSS刷题 js前端修改 os.path.join漏洞

打算刷一遍nssweb题&#xff08;任重道远&#xff09; 前面很简单 都是签到题 这里主要记录一下没想到的题目 [GDOUCTF 2023]hate eat snake js前端修改 这里 是对js的处理 有弹窗 说明可能存在 alert 我们去看看js 这里进行了判断 如果 getScore>-0x1e9* 我们结合上面…...

ArcGIS Maps SDK for JS:隐藏地图边框

文章目录 1 问题描述2 解决方案 1 问题描述 近期&#xff0c;将ArcGIS Api for JS v4.16更新到了ArcGIS Maps SDK for JS v4.27&#xff0c;原本去除地图的css代码失效了。 v4.26及以前版本 &#xff0c;需要用.esri-view-surface--inset-outline:focus::after 控制边框属性。…...

带你秒懂MySQL!! 一万字详细知识点和基础操作 欢迎评论区怼我 (三)

表操作 创建 # 创建表结构 create table user(id int comment ID,唯一标志,username varchar(20) comment 用户名,name varchar(10) comment 姓名,age int comment 年龄,gender char(1) comment 性别 ) comment 用户表; 约束 非空约束限制该字段值不为nullnot null唯一约束保证…...

kubeadmin部署k8s1.27.4

kubeadmin部署k8s1.27.4 环境介绍 IP主机名资源配置系统版本192.168.117.170k8s-master2c2g200gCentos7.9192.168.117.171k8s-node12c2g200gCentos7.9192.168.117.172k8s-node22c2g200gCentos7.9 编辑本地解析且修改主机名 三台主机都要做 vim /etc/hosts配置主机名 mast…...

【Aurix Tricore】HighTec启动代码crt0-tc37x.c分析笔记

1. 前言 crt0是hightec 在其toolchain的gcc库中实现启动startup功能的核心代码。 HighTec已为tc3xx设置了一些默认的启动行为。在此启动过程中,目标被初始化并设置为其默认值。启动文件的代码在进入main()函数之前执行。之后,执行main()函数的构造函数。 编译器附带的启动…...

Linux高级命令(扩展)

一、find命令 1、find命令作用 在Linux操作系统中&#xff0c;find命令主要用于进行文件的搜索。 2、基本语法 # find 搜索路径 [选项 选项的值] ... 选项说明&#xff1a; -name &#xff1a;根据文件的名称搜索文件&#xff0c;支持*通配符 -type &#xff1a;f代表普通文…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...