当前位置: 首页 > 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代表普通文…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...