第2章 算法分析基础
2-1 算法的时间复杂度分析
2.1.1 输入规模与基本语句
-
输入规模:算法处理数据的规模,通常用 n 表示。
-
基本语句:执行次数与输入规模直接相关的关键操作。
-
例2.1 顺序查找
int SeqSearch(int A[], int n, int k) { for (int i = 0; i < n; i++) if (A[i] == k) break; if (i == n) return 0; else return (i + 1); }
-
输入规模 n;基本语句是“比较 A[i] == k”
-
2.1.2 渐近分析
-
大 O、大 Ω、大 Θ
-
T(n)=O(f(n)):∃ c, n₀, ∀ n ≥ n₀, T(n) ≤ c·f(n)
-
T(n)=Ω(f(n)):∃ c, n₀, ∀ n ≥ n₀, T(n) ≥ c·f(n)
-
T(n)=Θ(f(n)):同时满足 O(f(n)) 和 Ω(f(n))
-
-
例:若 T(n) ≤ 100n + n 则 T(n)=O(n)
-
取 n₀=5, c=101, 则 ∀ n ≥ 5, T(n) ≤ 101n → O(n)
-
-
常见增长阶
1 < log n < n < n log n < n² < n³ < … < 2ⁿ < n! -
例2.4 合并算法
void Union(int A[], int n, int B[], int m, int C[]) {int i=0, j=0, k=0;while (i<n && j<m) {if (A[i] <= B[j]) C[k++] = A[i++];else C[k++] = B[j++];}while (i<n) C[k++] = A[i++];while (j<m) C[k++] = B[j++]; }
-
时间复杂度 O(n + m)
-
2.1.3 最好、最坏和平均情况
-
当算法执行代价依赖于不同输入时,需要分别分析:
-
最好情况:最少操作次数;
-
最坏情况:最多操作次数;
-
平均情况:所有输入实例上的平均操作次数。
-
-
顺序查找例
-
最好:第1个元素即中,比较1次;
-
最坏:未找到或在末尾,比较n次;
-
平均:约(n + 1)/2次
-
2-2 算法的空间复杂度分析
-
空间复杂度 = 输入/输出数据占用 + 算法本身占用 + 辅助空间
-
输入/输出数据:题目本身的数据结构;
-
算法本身:局部变量、常量,通常为 O(1);
-
辅助空间:临时数组、递归栈等。
-
-
示例
-
CommonFactor 求最大公约数:仅用常数级局部变量,O(1);
-
BubbleSort:只用固定数量的索引和临时变量,O(1);
-
Merge:需要长度为 n 的临时数组,O(n)。
-
2-3 算法的实验分析
-
实验分析:将算法实现为程序,上机运行,实际测算时空开销
-
常用度量方法
-
计数法:插入计数器,记录关键语句执行次数;
-
计时法:记录程序段开始和结束时间,计算时间差。
-
-
例 BubbleSort 实验
void BubbleSort(int r[], int n) {int j, temp, count1=0, count2=0, bound, exchange=n-1;while (exchange != 0) {bound = exchange; exchange = 0;for (j = 0; j < bound; j++)if (++count1 && r[j] > r[j+1]) {temp = r[j]; r[j] = r[j+1]; r[j+1] = temp;count2 += 3; exchange = j;}}cout<<"比较次数="<<count1<<",移动次数="<<count2<<endl; }
-
目的:统计比较次数和移动次数
-
-
Collatz 过程实验
-
规则:n 为奇数 → 3n+1,否则 → n/2,直到 n=1;
-
例 n=9:{9,28,14,…,1};
-
例 n=27:77步到9232,再32步到1。
-
2-4 拓展与演练:最优算法与下界
-
下界 Ω 表示法
若 ∃ c, n₀, ∀ n ≥ n₀, T(n) ≥ c·g(n),则 T(n)=Ω(g(n)),g(n) 是问题的时间下界 -
最优算法
如果问题已知下界 g(n),且算法满足 T(n)=Θ(g(n)),则该算法为最优。 -
例2.10 最小值算法
int ArrayMin(int a[], int n) {int min = a[0];for (int i = 1; i < n; i++)if (a[i] < min) min = a[i];return min; }
-
比较次数下界 Ω(n),算法时间 O(n),故为最优。
-
相关文章:
第2章 算法分析基础
2-1 算法的时间复杂度分析 2.1.1 输入规模与基本语句 输入规模:算法处理数据的规模,通常用 n 表示。 基本语句:执行次数与输入规模直接相关的关键操作。 例2.1 顺序查找 int SeqSearch(int A[], int n, int k) { for (int i 0; i < n…...
vue2 计算属性 computed
计算属性他是一个属性,他不是一个函数,使用的时候不要加括号 reduce reduce 是 JavaScript 数组的一个高阶函数,用于对数组中的每个元素执行一个累积计算,最终返回一个单一的值。...
Milvus 向量数据库详解与实践指南
一、Milvus 核心介绍 1. 什么是 Milvus? Milvus 是一款开源、高性能、可扩展的向量数据库,专门为海量向量数据的存储、索引和检索而设计。它支持近似最近邻搜索(ANN),适用于图像检索、自然语言处理(NLP&am…...
记录一次 python 文件环境变量配置-sqlmap.py
第一步:环境变量配置 C:\Users\14913\Downloads\application\3.secure\sqlmap-2025.5.6 或者 C:\Users\14913\Downloads\application\3.secure\sqlmap-2025.5.6 都可以! 第二步 使用 第一步:不再进目录 第二步:不再python … s…...
使用大语言模型进行机器人规划(Robot planning with LLMs)
李升伟 编译 长期规划在机器人学领域可以从经典控制方法与大型语言模型在现实世界知识能力的结合中获益。 在20世纪80年代,机器人学和人工智能(AI)领域的专家提出了莫雷奇悖论,观察到人类看似简单的涉及移动和感知的任务&#x…...
STM32 CAN总线
目录 定时传输CAN简介和硬件电路 CAN简介 主流通信协议对比 编辑 CAN硬件电路 编辑 CAN电平标准 CAN收发器 – TJA1050(高速CAN) CAN物理层特性 帧格式 数据帧 遥控帧 错误帧 过载帧 编辑 帧间隔 编辑 位填充 波形实例 位…...
使用JMeter 编写的测试计划的多个线程组如何生成独立的线程组报告
我有一个测试计划,里面有两个线程组,如下: 添加了一个HTTP请求默认值: 然后我使用如下命令生成的可视化报告是两个线程组合并后的聚合报告。 jmeter -n -t 百度测试计划.jmx -l baidu.txt -e -o ./baidu但是我想要的效果是每…...
RabbitMQ如何保证消息不丢失?
在RabbitMQ中,消息丢失可能发生在三个阶段:生产者发送消息时、消息在RabbitMQ服务器内部传递时、消费者接收消息时。为了保证消息不丢失,需要从这三个方面分别采取措施: 1. 生产者确保消息发送成功 开启确认模式(Conf…...
RAG 的介绍及评价方法
RAG的作用 大模型虽然具备处理复杂语言任务的强大能力,但在知识更新和依赖外部信息的及时性方面存在局限。大模型在训练时捕获的知识通常是静态的,一旦训练完成,模型便不再更新,无法掌握训练数据集之外的最新信息或事件。RAG可以…...
Linux网络新手注意事项与配置指南
Linux系统在网络管理方面提供了丰富的工具和灵活的配置方式,但对于新手来说,掌握正确的操作方法和注意事项至关重要。本文将从网络基础概念、配置工具、安全设置、故障排查以及常见错误等多个方面,结合具体代码示例,详细讲解Linux网络管理的核心内容,帮助新手快速入门并避…...
CI/CD与DevOps流程流程简述(提供思路)
一 CI/CD流程详解:代码集成、测试与发布部署 引言 在软件开发的世界里,CI/CD(持续集成/持续交付)就像是一套精密的流水线,确保代码从开发到上线的整个过程高效、稳定。我作为一名资深的软件工程师,接下来…...
【AWS+Wordpress-准备阶段】AWS注册+创建EC2实例
前言 自学笔记,解决问题为主,亲测有效,欢迎补充。 本地WP文件部署到AWS整体步骤如下:(本文重点:AWS准备完成) 0. [AWS 准备] 注册 AWS 并创建 EC2 实例 ↓ 1. [生成安装包:用 Du…...
FPGA----基于ZYNQ 7020实现定制化的EPICS通信系统
引言:前文我们降到了,使用alinx提供的sd卡,直接在上面编译即可。那么,如果我们的在FPGA侧有一些个性化的开发,那么生成的image.ub和boot.bin将于原sd卡中的不一致,我们应该如何坐呢? 补充知识点…...
读《暗时间》有感
读《暗时间》有感 反思与笔记 这本书还是我无意中使用 ima 给我写职业规划的时候给出的,由于有收藏的习惯,我就去找了这本书。当读到第一章暗时间的时候给了我很大的冲击,我本身就是一个想快速读完一本书的人,看到东西没有深入思…...
MIT关节电机相序校准
UVW三相相序判断 电机相序校正是确保多关节控制系统正常运行的重要步骤。在实际应用中,每个电机定子的三相线(W、U、V)的连接顺序可能存在差异,这是由于制造过程中的随机接线所致。不过,通过简单的校正方法,…...
Qwen2.5模型结构
self.lm_head nn.Linear(config.hidden_size, config.vocab_size, biasFalse) 这个是用来干嘛的 输出层,词汇投影层,将模型输出的隐藏状态向量映射回词表空间,用于预测下一个token # 预测 logits,未经过 softmax lm_logits self…...
2021-11-11 C++泰勒sin(x)以2步进乘方除以阶乘加减第N项
缘由c书本题,求解了,求解-编程语言-CSDN问答 int n 10, d 3, z -1; double x 2.5, xx x;while (n){xx (乘方(x, d) / 阶乘(d)) * z;d 2, --n, z * -1;}std::cout << xx << std::endl;...
【MySQL】C语言访问数据库
C语言访问数据库 一. Linux 安装 MySQL 动静态库二. 使用MySQL数据库1. 创建MySQL对象2. 连接MySQL数据库3. 释放MySQL对象4. SQL 语句操作1. 插入操作2. 修改操作3. 删除操作4. 查询操作 准备工作 use mysql; select user, host from user;# 创建本地连接的用户 create user c…...
dify 部署后docker 配置文件修改
1:修改 复制 ./dify/docker/.env.example ./dify/docker/.env 添加一下内容 # 启用自定义模型 CUSTOM_MODEL_ENABLEDtrue# 将OLLAMA_API_BASE_URL 改为宿主机的物理ip OLLAMA_API_BASE_URLhttp://192.168.72.8:11434# vllm 的 OPENAI的兼容 API 地址 CUSTOM_MODE…...
【神经网络与深度学习】VAE 和 GAN
这位大佬写的 VAE 的讲解很不错 VAE 和 GAN 的相同点和不同点 引言 VAE(变分自编码器)和 GAN(生成对抗网络)是深度学习中两种主要的生成模型,它们在数据生成任务中发挥着重要作用。虽然它们的目标相似,都…...
2-C#控件
2-控件 1.panel控件的使用 private void button3_Click(object sender, EventArgs e){Form2 my2 new Form2();my2.TopLevel false;this.panel1.Controls.Add(my2);my2.BringToFront();my2.Show();}private void button4_Click(object sender, EventArgs e){Form3 my3 new F…...
1.1.2 简化迭代器 yield return的使用
yield return 是一个用于简化迭代器(Iterator)实现的关键字组合。它的核心作用是让开发者能够以更简洁的方式定义一个按需生成序列的方法(生成器方法),而无需显式实现 IEnumerable 或 IEnumerator 接口。yield return …...
机器学习实操 第二部分 神经网路和深度学习 第14章 使用卷积神经网络进行深度计算机视觉
机器学习实操 第二部分 神经网路和深度学习 第14章 使用卷积神经网络进行深度计算机视觉 内容概要 第14章深入探讨了卷积神经网络(CNNs)及其在计算机视觉中的应用。CNNs受大脑视觉皮层的启发,通过局部感受野和权值共享机制,能够…...
电商双11美妆数据分析(2)
接下来用seaborn包给出每个店铺各个大类以及各个小类的销量销售额 关于性别 接下来考虑性别因素,了解各类产品在男性消费者中的销量占比 男士的销量基本来自于清洁类,其次是补水类。而这两类正是总销量中占比最高的两类。 非男士专用中,补水…...
数字康养新范式:七彩喜平台重构智慧养老生态的深度实践
在全球人口老龄化程度日益加深的当下,养老问题成为社会关注的焦点。 智慧养老作为一种创新的养老模式,借助现代信息技术,为提升老年人生活质量、缓解养老压力提供了新的思路与途径。 而当前中国 60 岁以上人口已达 2.8 亿,占总人…...
2D横板跳跃游戏笔记(查漏补缺ing...)
1.Compression(压缩质量):可以改为None,不压缩的效果最好,但占用内存 2.Filter Mode(过滤模式):可以选择Point(no filter) 3.Pixels Per Unit:是…...
c++中“”符号代表引用还是取内存地址?
c中,“&”符号有时代表引用,有时代表取地址符。 一、引用和取址 引用是一个已存在变量的别名,修改别名的值,原始变量的值也会改变;而取地址符则是得到一个指针,该指针指向变量的内存地址。 1&#x…...
AGV智能搬运机器人:富唯智能引领工业物流高效变革
在智能制造与工业4.0深度融合的今天,物流环节的高效与精准已成为企业核心竞争力的关键。富唯智能凭借其自主研发的AGV智能搬运机器人,以创新技术重塑工业物流标准,助力企业实现降本增效的跨越式发展。 一、技术突破:精准导航与智能…...
今年中国新能源汽车销量已破400万辆 大增42%
快科技5月7日消息,乘联分会公布了2025年4月新能源乘用车厂商批发销量数据。 纵观2025年以来,综合预估今年1-4月累计批发400万辆,同比增长42%。 根据中汽协发布的数据,2024年中国新能源汽车市场产销两旺,全年累计销量…...
广告屏蔽插件的内部细节EasyList 规则详解:为什么广告屏蔽不直接用 CSS/JS?(彩蛋)
广告屏蔽插件的内部细节:EasyList 规则详解;为什么广告屏蔽不直接用 CSS/JS屏蔽广告? 我们经常在浏览器中使用一些广告屏蔽插件(如 uBlock Origin、AdGuard、AdBlock Plus)已经成为许多用户的必备插件。 刚开…...
TCGA数据库临床亚型可用!贝叶斯聚类+特征网络分析,这篇 NC 提供的方法可以快速用起来了!
生信碱移 贝叶斯网络聚类 CANclust是一种基于贝叶斯的聚类方法,系统性地对基因突变、细胞遗传学信息和临床指标进行联合建模,用于多种模态数据的联合聚类分析,并识别在患者群体中反复出现的特征模式。 个体的遗传与环境背景决定其应对疾病的…...
好的软件系统
一个“好的软件系统”通常具有以下几个核心特征,简洁来说就是:“能用、好用、易维护、可扩展、安全可靠”。 一个好的软件系统,不只是“能跑起来”,而是“跑得稳、跑得快、跑得久,而且随时能换赛道还能继续跑 高内聚2.…...
某大型交通规划设计院转型实践:数智化破局复杂工程项目管理,实现高效人力资源一体化管理
随着中国经济的快速发展及基础设施建设的不断推进,交通规划设计行业正迎来新的机遇与挑战。作为行业的标杆企业,某大型交通规划设计院(以下简称G院)自1952年成立以来,始终致力于为公路、市政、建筑、园林规划等领域提供…...
格雷狼优化算法`GWO 通过模拟和优化一个信号处理问题来最大化特定频率下的功率
这段代码是一个Python程序,它使用了多个科学计算库,包括`random`、`numpy`、`matplotlib.pyplot`、`scipy.signal`和`scipy.signal.windows`。程序的主要目的是通过模拟和优化一个信号处理问题来最大化特定频率下的功率。 4. **定义类`class_model`**: - 这个类包含了信号…...
react中的用法——setDisabled dva dispatch effects
setDisabled 在react中,setDisabled通常是指通过状态管理来控制某个组件(如按钮、输入框等)的禁用状态。虽然react本身没有内置的setDisabled方法,但你可以使用useState钩子来实现类似的功能。以下是一个简单的示例,展…...
深入解析华为交换机中的VRRP原理
在现代网络架构中,高可用性和冗余性是确保网络稳定运行的关键因素。虚拟路由冗余协议(VRRP)作为一种广泛应用的冗余协议,能够有效地提升网络设备的可用性。特别是在华为交换机中,VRRP的实现为网络提供了更强大的灵活性…...
优艾智合CEO张朝辉荣膺U45杰出青年企业家
2025年是深圳经济特区成立45周年,也是深商会成立20周年。适逢五四青年节来临,深商总会、深圳市商业联合会、深圳市老字号协会、深圳市中小企业公共服务联盟、香港大湾区工商业联合会、广东省粤港澳大湾区产业协同发展联合会、深圳市深商公益基金会、深圳…...
解决HomeAssistant 无法安装 samba share问题
最近家里树莓派上的homeassistant 被折腾崩了,重新安装过程中发现加载项“Official add-ons”里面的“samba share”、“file edit”、“Mosquitto broker”等常用组件都不能安装。报以下错误: [supervisor.docker.interface] Cant install homeassista…...
【工具】HandBrake使用指南:功能详解与视频转码
HandBrake使用指南:功能详解与视频转码 一、前言 高清视频在当下日益普及,从影视制作到个人拍摄,从社交媒体发布到远程教育,如何高效地压缩、转换和管理视频文件的体积与清晰度,成为内容创作者与技术开发者的核心任务…...
代码随想录算法训练营第三十四天
LeetCode题目: 198. 打家劫舍213. 打家劫舍 II337. 打家劫舍 III3341. 到达最后一个房间的最少时间 I(每日一题) 其他: 今日总结 往期打卡 198. 打家劫舍 跳转: 198. 打家劫舍 学习: 代码随想录公开讲解 问题: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都…...
数字电子技术基础(五十五)——D触发器
1 D触发器 我们知道电平触发在CLK1、S1、R1的时候,有不确定的状态,输出会进入不稳定状态,这种情况下电路可能会导致逻辑错误,通过如果在时钟信号有效期间,如果S和R在此期间发生了多次变化,那么输出会随着发…...
Spark external shuffle service
yarn external shuffle service 参考链接: https://mp.weixin.qq.com/s/ZggMnX2r4uj8TrzUPTMLhQ shuffle过程包括shuffle read和shuffle write两个过程。对于spark on yarn,shuffle write是container写数据到本地磁盘(路径由core-site.xml中hadoop.tm…...
用 NGINX 打造高性能 FastCGI 加速 `ngx_http_fastcgi_module`
一、安装与启用 # 在编译 NGINX 源码时加上: ./configure --with-http_fastcgi_module make && sudo make install# 或确保你使用的二进制已内置(大多数发行版都默认包含) nginx -V | grep fastcgi二、基础转发配置 http {server {…...
penEuler操作系统结合豆包测试github仓库8086-Emulator项目
penEuler操作系统结合豆包测试github仓库8086-Emulator项目 8086-Emulator项目:https://github.com/YJDoc2/8086-Emulator 申请空间 首先在华为开发者空间申请一个免费云主机(penEuler操作系统):https://huaweicloud.csdn.net/…...
MapReduce中的分区器
在MapReduce框架中,分区器(Partitioner)是一个关键组件,其主要作用是决定由一个maptask生成的键值,最终是生成在哪个文件中的。 默认的分区器是HashPartitioner,它会根据键的哈希值将数据均匀分配到各个Red…...
【愚公系列】《Manus极简入门》024-表演艺术教练:“舞台魔法师”
🌟【技术大咖愚公搬代码:全栈专家的成长之路,你关注的宝藏博主在这里!】🌟 📣开发者圈持续输出高质量干货的"愚公精神"践行者——全网百万开发者都在追更的顶级技术博主! …...
CentOS 系统升级失败的原因与排查
一、常见升级失败原因 1. 软件包依赖问题 循环依赖:软件包A依赖B,B又依赖A 版本冲突:新旧版本软件包不兼容 缺失依赖:所需依赖包未正确安装或不可用 2. 存储空间不足 /boot分区空间不足(常见于内核更新࿰…...
【useOperatorData Hook 改造实践】
useOperatorData Hook 改造实践 1. 背景 在我们的大屏项目中,运营商数据是一个核心的业务概念。几乎所有业务模块都需要根据当前选择的运营商来获取对应的数据。这就要求我们有一个统一的、可靠的方式来处理运营商相关的数据获取和状态变更。 1.1 原有实现 最初…...
vue3+ts的computed属性怎么用?
首先我们要进行引入computed这个属性,然后定义用这个属性的时候我们要先了解这个属性。 这个computed其实分为里两种!一种是仅可读的,还有一种就是即可以读,又可以修改的! 那我们常用的肯定是后者!我们引…...
游戏服务器怎么挑选细节与技巧深度解析
在开发或运营网络游戏时,选择合适的游戏服务器是决定游戏体验和运营成败的关键因素。本文将深入分析游戏服务器挑选的核心考量点和实用技巧。 一、基础架构选择 1. 服务器类型对比 类型物理服务器云服务器混合架构 优势完全控制权、高性能稳定弹性扩展、全球部署…...