数据结构.1时间与空间复杂度-北京尧图网络

文章目录1. 算法效率1.1 什么是时间复杂度1.2 常见结构的基本复杂度1.2.1 O(1)1.2.2 O(n)1.2.3 O(n²)1.2.4 O(log n)1.2.5 O(n log n)2. 什么是空间复杂度2.1 计算空间复杂度的三条前提前提一只算额外空间前提二看峰值不看累计前提三递归栈也要算2.2 O(1)2.3 O(n)2.4 空间复杂度速查表2.5 时间与空间的权衡3. 小结1. 算法效率当我们评价一个算法的优劣时通常会通过算法效率来评估。算法效率分为两部分时间效率算法运行时耗费的时间空间效率算法运行过程中额外耗费的存储空间但由于运行环境电脑性能、编程语言、编译器优化存在差异同一份代码在不同机器上的实际耗时可能相差几十倍直接测量并不可靠。因此我们通常采用事前分析估算的方法由此引出时间复杂度和空间复杂度。1.1 什么是时间复杂度通俗地讲时间复杂度就是当输入数据量变大时这段代码的运行时间增长得有多快。它不关心「跑一次要几秒」只关心「数据量翻倍时时间涨几倍」。常见从小到大排列O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ) O(n!)1.2 常见结构的基本复杂度代码结构操作次数复杂度几条语句与 n 无关常数O(1)for (i 0; i n; i)套一层nO(n)两层都跑 n 次n × nO(n²)每层 n但内层只跑到一半n²/2O(n²)每次砍一半n→n/2→n/4log₂nO(log n)1.2.1 O(1)与 n 无关的固定几条语句。voidswap(int*a,int*b){inttemp*a;*a*b;*btemp;}intis_leap(intyear){return(year%40year%100!0)||year%4000;}1.2.2 O(n)单层循环intfind_max(int*arr,intn){intmax_valarr[0];// 1 次for(inti0;in;i)// n 次if(arr[i]max_val)// 每次 1 次比较max_valarr[i];// 偶尔 1 次returnmax_val;}递归intsum_to_n(intn){if(n0)return0;returnnsum_to_n(n-1);}1.2.3 O(n²)两层都跑满for(inti0;in;i)for(intj0;jn;j)count;// n × n n² 次内层只跑一半for(inti0;in;i)for(intji;jn;j)count;// n (n-1) … 1 n(n1)/2 次1.2.4 O(log n)每轮折半intcount0;intxn;while(x0){count;x/2;}1.2.5 O(n log n)外层 n 次内层折半for(inti0;in;i){// 外层 n 次intxi;while(x0){// 内层 log i 次count;x/2;}}2. 什么是空间复杂度和时间复杂度类似空间复杂度也采用事前分析估算的方法衡量的是当输入规模 n 增大时算法额外占用的内存增长得有多快。计算方法与时间复杂度基本一致但有三条特有规则。2.1 计算空间复杂度的三条前提前提一只算额外空间默认不计入输入数据本身只算算法为了完成计算而额外申请的空间即辅助空间auxiliary space。intfind_max(int*arr,intn){intmax_valarr[0];// 唯一的额外变量for(inti0;in;i)if(arr[i]max_val)max_valarr[i];returnmax_val;}输入arr占O(n)但那是输入自带的。算法额外只用 1 个变量故空间复杂度为O(1)。前提二看峰值不看累计voidrun(intn){int*amalloc(n*sizeof(int));// 申请 n 个free(a);int*bmalloc(n*sizeof(int));// 再申请 n 个free(b);}累计申请了2n个元素但任何时刻最多只有 n 个同时存在所以空间复杂度是O(n)而不是O(2n)。前提三递归栈也要算intfact(intn){if(n1)return1;returnn*fact(n-1);}函数里只有一个参数看似O(1)实际是O(n)。因为每层递归都要把参数、返回地址、局部变量压入调用栈n 层调用同时存在栈深度 n故空间复杂度为O(n)。2.2 O(1)只使用固定几个变量称为原地in-place算法。voidswap(int*a,int*b){intt*a;*a*b;*bt;}voidreverse(int*arr,intn){inti0,jn-1;while(ij){inttarr[i];arr[i]arr[j];arr[j]t;i;j--;}}不论 n 是 10 还是 1000 万额外内存始终是几个字节故为O(1)。冒泡、插入、选择、堆排序都是O(1)空间的原地排序这是它们的重要优势。2.3 O(n)辅助数组int*copy_array(int*src,intn){int*dstmalloc(n*sizeof(int));for(inti0;in;i)dst[i]src[i];returndst;}新数组包含 n 个元素故为O(n)。递归深度为 nintsum_rec(intn){if(n0)return0;returnnsum_rec(n-1);}这里的分析重点不是时间而是空间时间每层做一次加法共 n 层 →O(n)空间n 层栈帧同时存在 →O(n)注意同一个函数可以有两个不同的复杂度。时间看「调用了多少次」空间看「同时存在多少层」。这正是 1.2.2 与 2.4 使用相似代码的原因。2.4 空间复杂度速查表写法空间复杂度几个局部变量O(1)| 一维数组 n 个元素 |O(n)|| 递归深度为 n |O(n)|2.5 时间与空间的权衡算法设计中时间和空间往往不能同时最优需要取舍因此「用空间换时间」是工程中最常见的优化方向因为内存通常比 CPU 时间便宜。3. 小结时间复杂度数操作次数随 n 的增长趋势。顺序相加、嵌套相乘、分支取最大、递归写递推式最后化简只留最高阶。空间复杂度数额外内存的峰值随 n 的增长趋势。只算额外空间看峰值不看累计递归要算栈深度。两者都是事前估算衡量的是增长趋势而非具体耗时或占用。判断依据是次数不是循环层数系数和常数不影响量级。

数据结构.1时间与空间复杂度

相关推荐

超越检索：企业 RAG 的生产级系统设计

IPv4/IPv6寻址翻译器：从NAT64/DNS64原理到实战配置

网格EA交易法：带止损纪律的机械仓位管理术

更多资讯

知识工作插件化：构建可编程、可组合的智能工作流底座

SQL题目面试避坑指南：从读题拆解到查询优化全链路

知识工作插件：面向知识工作者的模块化增强协议

SchoolDB四表DDL全解析：数据库设计从字段选择到约束实践

订单表慢SQL优化实战：联合索引、覆盖索引与深分页方案

Python实战英雄联盟胜率预测：从数据清洗到SHAP模型解释

今日更新

微信云开发旅游小程序实战：LBS打卡+UGC社交全栈方案

金融AI代理平台核心拆解：从多代理协作到财报分析实战

基于大数据的智慧旅游推荐与可视化平台架构实践

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？