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

2026《数据结构》考研复习笔记四(第一章)

绪论

  • 前言
  • 时间复杂度分析

前言

由于先前笔者花费约一周时间将王道《数据结构》知识点大致过了一遍,圈画下来疑难知识点,有了大致的知识框架,现在的任务就是将知识点逐个理解透彻,并将leetcode刷题与课后刷题相结合。因此此后的过程中,整理的笔记不仅包含课本知识点,还包含经典课后题讲解(主要是笔者认为重要的)以及leetcode代码(用于深入理解重要知识点)。综上,复习思路为:大致过一遍知识点有个系统框架->写代码深入理解->刷题适应考试模式

经复习,我将本书大致分为四部分——第一章:绪论(主要是算法效率的度量),第二章+第三章+第四章:线性结构(包括数组、链表、栈、队列以及串),第五章+第六章:非线性结构(包括树、图),第七章+第八章:实际应用(包括顺序查找、树形查找、散列查找以及各种排序算法)。

本篇文章为第一部分,除了一些零散的概念性知识,只有一个较为重要的考点——时间复杂度分析。记住结论即可,有兴趣的同学可以自行推理(本来是想写一下的,但是太费时间了,而且估计看的人不多,所以自行推理吧)

时间复杂度分析

我们将循环分为两种类型——等差递增和等比递增(递减可以转化为递增)。常见形式如:

  • 等差递增:for(int i=0;i<n;i++)
  • 等比递增:for(int i=1;i<n;i*=2)

为了找出一般规律,我们接下来探究等差递增和等比递增的一般形式:

  • 等差递增:for(int i=a0;i<n;i+=d)。其中a0为首项,d为等差
  • 等比递增:for(int i=a0;i<n;i*=q)。其中a0为首项,q为等比

一、单层for循环

类型 时间复杂度
等差for(int i=a~0~;i< n;i+=d) O(n)
等比for(int i=a~0~;i< n;i*=q) O(logn)

推导过程:
(假设运行次数为t,即最后一次运行i=at
1.对于等差递增,有n-d<=at<n,即n-d<=a0+t * d<n,推导出(n-d-a0)/d<=t<(n-a0)/d,忽略常数,有时间复杂度为O(n)
2.对于等比递增,有n/q<=at<n,即n/q<=a0 * qt<n,推导出logq(n/(q * a0))<=t<logq(n/a0),经过换底公式后忽略常数,有时间复杂度为O(logn)

二、双层for循环
首先将双层for循环分为两种类型:

  • 上下变量无关:上层递增变量与下层递增变量没有直接关系。如:
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
  • 上下变量有关:下层递增变量依赖于上层递增变量。如:
    for(int i=0;i<n;i++)
    for(int j=0;j<i;j++)//j的初始值为i

    同时我们将递增类型分为两种类型:
  • 加法(等差递增):for(int i=a0;i<n;i+=d)。其中a0为首项,d为等差
  • 乘法(等比递增):for(int i=a0;i<n;i*=q)。其中a0为首项,q为等比

假设两层for循环的判断条件都是n(即i<n、j<n):

上下变量无关

第一层for循环 第二层for循环 时间复杂度
乘法 乘法 O(log2n)
乘法 加法 O(nlogn)
加法 乘法 O(nlogn)
加法 加法 O(n2)

上下变量有关

第一层for循环 第二层for循环 时间复杂度
乘法 乘法 O(log2n)
乘法 加法 O(n)
加法 乘法 O(nlogn)
加法 加法 O(n2)

仅有先乘后加的时候有区别,前者为O(nlogn)后者为O(n)——参见2022统考真题,其中便考察了这个知识点

注意:对于上下变量有关,第一层为加法,第二层为乘法的时候,最终的时间复杂度为O(logn!),根据斯特林公式,n!≈√(2nπ)(n/e)n,取对数后化简为nlogn

至于上下for循环参数不一致,在此也不再讨论(出题概率较低)

相关文章:

2026《数据结构》考研复习笔记四(第一章)

绪论 前言时间复杂度分析 前言 由于先前笔者花费约一周时间将王道《数据结构》知识点大致过了一遍&#xff0c;圈画下来疑难知识点&#xff0c;有了大致的知识框架&#xff0c;现在的任务就是将知识点逐个理解透彻&#xff0c;并将leetcode刷题与课后刷题相结合。因此此后的过…...

Mysql insert一条数据的详细过程

以下是MySQL在接收到INSERT语句后存储数据的详细过程解析&#xff0c;结合存储引擎&#xff08;以InnoDB为例&#xff09;和物理存储机制分步说明。 一、SQL解析与事务启动 1.语法解析 MySQL首先解析INSERT语句&#xff0c;验证字段是否存在、数据类型是否匹配、约束&#xf…...

流水灯右移程序(STC89C52单片机)

#include <reg52.h> sbit ADDR0 P1^0; sbit ADDR1 P1^1; sbit ADDR2 P1^2; sbit ADDR3 P1^3; sbit ENLED P1^4; void main() { unsigned int i 0; //定义循环变量i&#xff0c;用于软件延时 unsigned char cnt 0; //定义计数变量cnt&#xff0c;用…...

AI-Sphere-Butler之如何使用Llama factory LoRA微调Qwen2-1.5B/3B专属管家大模型

环境&#xff1a; AI-Sphere-Butler WSL2 英伟达4070ti 12G Win10 Ubuntu22.04 Qwen2.-1.5B/3B Llama factory llama.cpp 问题描述&#xff1a; AI-Sphere-Butler之如何使用Llama factory LoRA微调Qwen2-1.5B/3B管家大模型 解决方案&#xff1a; 一、准备数据集我这…...

智能体团队 (Agent Team)

概述 智能体团队是一种多智能体协作模式&#xff0c;它将多个智能体组织成一个团队&#xff0c;共同解决复杂任务。与智能体监督模式不同&#xff0c;智能体团队中的成员通常具有平等的地位&#xff0c;通过相互交流和协作来达成目标。这种模式特别适合需要多种观点或多领域专…...

AI日报 - 2025年04月19日

&#x1f31f; 今日概览(60秒速览) ▎&#x1f916; AGI突破 | OpenAI与Google模型在复杂推理上展现潜力&#xff0c;但距AGI仍有距离&#xff1b;因果AI被视为关键路径。 模型如o3解决复杂迷宫&#xff0c;o4-mini通过棋盘测试&#xff0c;但专家预测AGI仍需30年。 ▎&#x1…...

【实战中提升自己】内网安全部署之dot1x部署 本地与集成AD域的主流方式(附带MAC认证)

1 dot1x部署【用户名密码认证&#xff0c;也可以解决私接无线AP等功能】 说明&#xff1a;如果一个网络需要通过用户名认证才能访问内网&#xff0c;而认证失败只能访问外网与服务器&#xff0c;可以部署dot1x功能。它能实现的效果是&#xff0c;当内部用户输入正常的…...

算法—合并排序—js(场景:大数据且需稳定性)

合并排序基本思想&#xff08;稳定且高效&#xff09; 将数组递归拆分为最小单元&#xff0c;合并两个有序数组。 特点&#xff1a; 时间复杂度&#xff1a;O(n log n) 空间复杂度&#xff1a;O(n) 稳定排序 // 合并排序-分解 function mergeSort(arr) {if (arr.length < …...

绝对路径与相对路径

绝对路径和相对路径是在计算机系统中用于定位文件或目录的两种方式&#xff0c;以下是具体介绍&#xff1a; 绝对路径 • 定义&#xff1a;是从文件系统的根目录开始到目标文件或目录的完整路径&#xff0c;它包含了从根目录到目标位置的所有目录和子目录信息&#xff0c;具有…...

RabbitMQ,添加用户时,出现Erlang cookie不一致,导致添加用户失败的问题解决

1. 问题现象 RabbitMQ 添加用户&#xff0c;出现以下报错 ./rabbitmgctl add user admin admin666*2. 问题原因和解决方法 安装的 RabbitMQ 里的 Erlang cookie&#xff0c;和 Erlang 环境的 cookie 不一致导致的 解决方法&#xff1a;将 Erlang 环境的 cookie &#xff0c…...

阿拉丁神灯-第16届蓝桥第4次STEMA测评Scratch真题第2题

[导读]&#xff1a;超平老师的《Scratch蓝桥杯真题解析100讲》已经全部完成&#xff0c;后续会不定期解读蓝桥真题&#xff0c;这是Scratch蓝桥真题解析第219讲。 第16届蓝桥第4次STEMA测评已于2025年1月12日落下帷幕&#xff0c;编程题一共有5题&#xff08;初级组只有前4道编…...

常用的验证验证 onnxruntime-gpu安装的命令

#工作记录 我们经常会遇到明明安装了onnxruntime-gpu或onnxruntime后&#xff0c;无法正常使用的情况。 一、强制重新安装 onnxruntime-gpu 及其依赖 # 强制重新安装 onnxruntime-gpu 及其依赖 pip install --force-reinstall --no-cache-dir onnxruntime-gpu1.18.0 --extra…...

docker配置skywalking 监控springcloud应用

在使用 Docker 配置 SkyWalking 监控 Spring Cloud 应用时&#xff0c;主要分为以下几个步骤&#xff1a; 1. 准备工作 确保你的开发环境已经安装了 Docker 和 Docker Compose。准备好 Spring Cloud 应用代码&#xff0c;并确保它支持 SkyWalking 的探针&#xff08;Agent&…...

HBase安装与基本操作指南

## 1. 安装准备 首先确保您的系统已经安装了以下组件: - Java JDK 8或更高版本 - Hadoop(HBase可以运行在独立模式下,但建议配合Hadoop使用) ## 2. 下载与安装HBase ```bash # 下载HBase(以2.4.12版本为例) wget https://downloads.apache.org/hbase/2.4.12/hbase-2…...

【Linux】Rhcsa复习5

一、Linux文件系统权限 1、文件的一般权限 文件权限针对三类对象进行定义&#xff1a; owner 属主&#xff0c;缩写u group 属组&#xff0c; 缩写g other 其他&#xff0c;缩写o 每个文件针对每类访问者定义了三种主要权限&#xff1a; r&#xff1a;read 读 w&…...

C++11特性补充

目录 lambda表达式 定义 捕捉的方式 可变模板参数 递归函数方式展开参数包 数组展开参数包 移动构造和移动赋值 包装器 绑定bind 智能指针 RAII auto_ptr unique_ptr shared_ptr 循环引用 weak_ptr 补充 总结 特殊类的设计 不能被拷贝的类 只能在堆上创建…...

缓存 --- Redis性能瓶颈和大Key问题

缓存 --- Redis性能瓶颈和大Key问题 内存瓶颈网络瓶颈CPU 瓶颈持久化瓶颈大key问题优化方案 Redis 是一个高性能的内存数据库&#xff0c;但在实际使用中&#xff0c;可能会在内存、网络、CPU、持久化、大键值对等方面遇到性能瓶颈。下面从这些方面详细分析 Redis 的性能瓶颈&a…...

css3新特性第三章(文本属性)

一、文本属性 文本阴影文本换行文本溢出文本修饰文本描边 1.1 文本阴影 在 CSS3 中&#xff0c;我们可以使用 text-shadow 属性给文本添加阴影。 语法&#xff1a; text-shadow: h-shadow v-shadow blur color; 值描述h-shadow必需写&#xff0c;水平阴影的位置。允许负值。…...

Redis 缓存—处理高并发问题

Redis的布隆过滤器、单线程架构、双写一致性、比较穿透、击穿及雪崩、缓存更新方案及分布式锁。 1 布隆过滤器 是一种高效的概率型数据结构&#xff0c;用于判断元素是否存在。主要用于防止缓存穿透&#xff0c;通过拦截不存在的数据查询&#xff0c;避免击穿数据库。 原理&…...

嵌入式芯片中的 SRAM 内容细讲

什么是 RAM&#xff1f; RAM 指的是“随机存取”&#xff0c;意思是存储单元都可以在相同的时间内被读写&#xff0c;和“顺序访问”&#xff08;如磁带&#xff09;相对。 RAM 不等于 DRAM&#xff0c;而是一类统称&#xff0c;包括 SRAM 和 DRAM 两种主要类型。 静态随机存…...

实操基于MCP驱动的 Agentic RAG:智能调度向量召回或者网络检索

我们展示了一个由 MCP 驱动的 Agentic RAG&#xff0c;它会搜索向量数据库&#xff0c;当然如果有需要他会自行进行网络搜索。 为了构建这个系统&#xff0c;我们将使用以下工具&#xff1a; 博查搜索 用于大规模抓取网络数据。作为Faiss向量数据库。Cursor 作为 MCP 客户端。…...

位运算---总结

位运算 基础 1. & 运算符 : 有 0 就是 0 2. | 运算符 : 有 1 就是 1 3. ^ 运算符 : 相同为0 相异为1 and 无进位相加位运算的优选级 不用在意优先级,能加括号就加括号给一个数 n ,确定它的二进制位中第 x 位是 0 还是 1? 规定: 题中所说的第x位指:int 在32位机器下4个…...

从0开始搭建一套工具函数库,发布npm,支持commonjs模块es模块和script引入使用

文章目录 文章目标技术选型工程搭建1. 初始化项目2. 安装开发依赖3. 项目结构4. 配置文件tsconfig.json.eslintrc.jseslint.config.prettierrc.jsrollup.config.cjs创建 .gitignore文件 设置 Git 钩子创建示例工具函数8. 版本管理和发布9 工具函数测试方案1. 安装测试依赖2. 配…...

精通 Spring Cache + Redis:避坑指南与最佳实践

Spring Cache 以其优雅的注解方式&#xff0c;极大地简化了 Java 应用中缓存逻辑的实现。结合高性能的内存数据库 Redis&#xff0c;我们可以轻松构建出响应迅速、扩展性强的应用程序。然而&#xff0c;在享受便捷的同时&#xff0c;一些常见的“坑”和被忽视的最佳实践可能会悄…...

DSP28335入门学习——第一节:工程项目创建

写这个文章是用来学习的,记录一下我的学习过程。希望我能一直坚持下去,我只是一个小白,只是想好好学习,我知道这会很难&#xff0c;但我还是想去做&#xff01; 本文写于&#xff1a;2025.04.20 DSP28335开发板学习——第一节&#xff1a;工程项目创建 前言开发板说明引用解答…...

Docker Registry(镜像仓库)

官方架构 Docker 使用客户端 - 服务器 (C/S) 架构模式&#xff0c;使用远程 API 来管理和创建 Docker 容器。Docker 容器通过 Docker 镜像来创建。 Docker 仓库(Registry)&#xff1a;Docker 仓库用来保存镜像&#xff0c;可以理解为代码控制中的代码仓库。Docker Hu…...

通过Dify快速搭建本地AI智能体开发平台

1. 安装Docker Desktop 访问 Docker官网 点击Download Docker Desktop&#xff0c;直接按照官方要求来就可以。 # 这串命令就像魔法咒语&#xff0c;在黑色窗口&#xff08;命令提示符&#xff09;里输入就能检查安装是否成功 docker --version2.安装dify 3.运行 Ollama 大…...

计算机视觉与深度学习 | Transformer原理,公式,代码,应用

Transformer 详解 Transformer 是 Google 在 2017 年提出的基于自注意力机制的深度学习模型,彻底改变了序列建模的范式,解决了 RNN 和 LSTM 在长距离依赖和并行计算上的局限性。以下是其原理、公式、代码和应用的详细解析。 一、原理 核心架构 Transformer 由 编码器(Encod…...

skywalking agent 关联docker镜像

Apache SkyWalking 提供了多种方式来部署和使用 SkyWalking Agent&#xff0c;包括在 Docker 容器中运行的应用。虽然 SkyWalking Agent 本身不是一个独立的 Docker 镜像&#xff0c;但你可以通过几种方式将 SkyWalking Agent 集成到你的 Docker 应用中。 方式一&#xff1a;手…...

【中间件】nginx将请求负载均衡转发给网关,网关再将请求转发给对应服务

一、场景 前端将请求发送给nginx&#xff0c;nginx将请求再转发给网关&#xff0c;网关再将请求转发至对应服务。由于网关会部署在多台服务器上&#xff0c;因此nginx需要负载均衡给网关发请求。nginx所有配置均参照官方文档nginx开发文档&#xff0c;可参考负载均衡板块内容 二…...

Milvus(1):什么是 Milvus

Milvus 由 Zilliz 开发&#xff0c;并很快捐赠给了 Linux 基金会下的 LF AI & Data 基金会&#xff0c;现已成为世界领先的开源向量数据库项目之一。它采用 Apache 2.0 许可发布&#xff0c;大多数贡献者都是高性能计算&#xff08;HPC&#xff09;领域的专家&#xff0c;擅…...

第十六节:高频开放题-React与Vue设计哲学差异

响应式原理&#xff08;Proxy vs 虚拟DOM&#xff09; 组合式API vs Hooks React 与 Vue 设计哲学差异深度解析 一、响应式原理的底层实现差异 1. Vue 的响应式模型&#xff08;Proxy/数据劫持&#xff09; Vue 的响应式系统通过 数据劫持 实现自动依赖追踪&#xff1a; • …...

【Hot100】 240. 搜索二维矩阵 II

目录 引言搜索二维矩阵 II我的解题贪心求解解题思路详解搜索策略&#xff08;以从右上角开始为例&#xff09;为什么这种方法有效&#xff1f; 完整代码实现复杂度分析示例演示 &#x1f64b;‍♂️ 作者&#xff1a;海码007&#x1f4dc; 专栏&#xff1a;算法专栏&#x1f4a…...

每日面试实录·携程·社招·JAVA

&#x1f4cd;面试公司&#xff1a;携程 &#x1f45c;面试岗位&#xff1a;后端开发工程师&#xff08;社招&#xff09; &#x1f550;面试时长&#xff1a;约 50 分钟 &#x1f504;面试轮次&#xff1a;第 1 轮技术面 ✨面试整体节奏&#xff1a; 这场携程的社招 Java 一面…...

Oracle--用户管理

前言&#xff1a;本博客仅作记录学习使用&#xff0c;部分图片出自网络&#xff0c;如有侵犯您的权益&#xff0c;请联系删除 用户管理在 Oracle 数据库中至关重要。一个服务器通常只运行一个 Oracle 实例&#xff0c;而一个 Oracle 用户代表一个用户群&#xff0c;他们通过该用…...

20.3 使用技巧5

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的 20.3.8 CellContentClick事件 当增加新按钮列或者超链接列后&#xff0c;按钮或者超链接&#xff0c;会发现&#xff0c;按钮或者超链…...

Kubernetes相关的名词解释Metrics Server组件(7)

什么是Metrics Server&#xff1f; Metrics Server 是 Kubernetes 集群中的一个关键组件&#xff0c;主要用于资源监控和自动扩缩容。 kubernetes 从1.8版本开始不再集成cadvisor&#xff0c;也废弃了heapster&#xff0c;使用metrics server来提供metrics。那么...... 什么…...

17.【.NET 8 实战--孢子记账--从单体到微服务--转向微服务】--单体转微服务--SonarQube部署与配置

在将孢子记账系统从单体架构转向微服务架构的过程中&#xff0c;代码质量的管理变得尤为重要。随着项目规模的扩大和团队协作的深入&#xff0c;我们需要一个强大的工具来帮助我们持续监控和改进代码质量。我们首选SonarQube&#xff0c;它能够帮助我们识别代码中的潜在问题、技…...

计算机是如何看待数据的?

一、计算机如何“看待”数据&#xff1f; 物理层本质&#xff1a; 计算机的所有数据最终以二进制&#xff08;0和1&#xff09;在电路中表示&#xff08;高电平1&#xff0c;低电平0&#xff09;。 无论你用何种进制描述数据&#xff08;如十六进制 0xA1 或十进制 161&#xf…...

25.4.20学习总结

如何使用listView组件来做聊天界面 1. 什么是CellFactory&#xff1f; 在JavaFX中&#xff0c;控件&#xff08;比如ListView、TableView等&#xff09;用Cell来显示每一条数据。 Cell&#xff1a;代表这个单元格&#xff08;即每个列表项&#xff09;中显示的内容和样式。 …...

SpringBoot3集成ES8.15实现余额监控

1. gradle依赖新增 implementation org.springframework.boot:spring-boot-starter-data-elasticsearch implementation co.elastic.clients:elasticsearch-java:8.15.02. application.yml配置 spring:elasticsearch:uris: http://localhost:9200username: elasticpassword: …...

STM32基础教程——串口收发

目录 前言 字长设置 ​编辑 停止位 起始位侦测 波特率 1. UART波特率的基本原理 2. 为什么需要先除以分频因子&#xff08;USARTDIV&#xff09;&#xff1f; &#xff08;1&#xff09;PCLK频率太高 &#xff08;2&#xff09;分频因子的作用 3. 为什么还需要再除以…...

Matlab 步进电机传递函数模糊pid

1、内容简介 Matlab 210-步进电机传递函数模糊pid 可以交流、咨询、答疑 2、内容说明 略 3、仿真分析 略 4、参考论文 略...

unordered_map、unordered_set详解

深入理解C中的 unordered_map 和 unordered_set 在C标准库中&#xff0c;unordered_map 和 unordered_set 是两个基于‌哈希表&#xff08;Hash Table&#xff09;‌实现的高效容器。它们以‌O(1)‌的平均时间复杂度实现快速查找、插入和删除操作&#xff0c;特别适合需要高频…...

详解trl中的GRPOTrainer和GRPOConfig

引言 在大型语言模型(LLM)的强化学习微调领域, Group Relative Policy Optimization (GRPO) 算法因其高效性和资源友好性受到广泛关注。Hugging Face的 TRL (Transformer Reinforcement Learning) 库通过GRPOTrainer和GRPOConfig提供了该算法的开箱即用实现。本文将深入解析…...

【C++】多态 - 从虚函数到动态绑定的核心原理

&#x1f4cc; 个人主页&#xff1a; 孙同学_ &#x1f527; 文章专栏&#xff1a;C &#x1f4a1; 关注我&#xff0c;分享经验&#xff0c;助你少走弯路 文章目录 1. 多态的概念2. 多态的定义及实现2.1 多态的构成条件2.1.1实现多态还有两个必须重要条件&#xff1a;2.1.2 虚…...

项目预期管理:超越甘特图,实现客户价值交付

引言 在项目管理实践中&#xff0c;许多项目经理习惯于将注意力集中在甘特图的进度条上&#xff0c;关注任务是否按时完成、里程碑是否达成。然而&#xff0c;这种以计划管理为中心的方法往往忽略了项目管理的核心目标&#xff1a;满足客户预期&#xff0c;交付真正的价值。项…...

FISCO 2.0 安装部署WeBASE与区块链浏览器(环境搭建)

FISCO BCOS 2.0 安装部署WeBASE与区块链浏览器-对应的官网地址&#xff1a; WeBASE平台&#xff1a;https://webasedoc.readthedocs.io/zh-cn/latest/docs/WeBASE/install.html 区块链浏览器&#xff1a;https://fisco-bcos-documentation.readthedocs.io/zh-cn/latest/docs/br…...

xss学习3之服务端session

一、服务端的Session 1. cookie和session 1&#xff09;cookie和session对比 cookie: 保存在客户端&#xff0c;包含所有key-value信息&#xff0c;浏览器访问多个网站时会积累大量cookie&#xff0c;占用存储空间&#xff0c;并在每次请求时携带所有cookie&#xff0c;增加…...

23种设计模式-结构型模式之适配器模式(Java版本)

Java 适配器模式&#xff08;Adapter Pattern&#xff09;详解 &#x1f50c; 什么是适配器模式&#xff1f; 适配器模式用于将一个类的接口转换成客户端所期望的另一种接口&#xff0c;让原本接口不兼容的类可以协同工作。 &#x1f4e6; 就像插头转换器&#xff0c;让不同…...