数据结构入门必学：时间复杂度、空间复杂度详细解析（附实例代码）-云帆数科

前言在学习算法的时候我们经常会遇到一个问题为什么两个程序实现相同功能一个运行非常快一个却非常慢例如斐波那契数列long long Fib(int N) { if(N 3) return 1; return Fib(N-1)Fib(N-2); }代码非常简洁但是当数据规模变大时运行效率会快速下降。所以判断一个算法是否优秀不能只看代码量而要分析算法效率。算法效率主要从两个方面衡量时间复杂度空间复杂度一、什么是算法复杂度算法运行时会消耗1. 时间资源也就是程序运行需要多久。对应时间复杂度2. 空间资源也就是程序运行过程中需要多少额外内存。对应空间复杂度因此算法复杂度衡量算法效率的重要指标。二、时间复杂度详解1. 时间复杂度是什么时间复杂度不是计算程序运行多少秒。因为不同机器CPU不同编译器不同环境不同运行时间都会变化。所以算法分析采用基本操作执行次数与问题规模N之间的关系例如void Func(int N) { for(int i0;iN;i) { count; } }执行次数N次因此时间复杂度 O(N)三、大O渐进表示法实际计算中我们不会关注精确次数。例如F(N)N²2N10如何表示第一步去掉常数N²2N第二步保留最高阶N²第三步去掉系数O(N²)最终时间复杂度 O(N²)四、常见时间复杂度1️⃣ O(1)常数阶int a10;执行次数不会随着N变化。2️⃣ O(N)线性阶for(int i0;iN;i) { }执行N次。3️⃣ O(N²)平方阶for(int i0;iN;i) { for(int j0;jN;j) { } }执行N*N次。4️⃣ O(logN)典型二分查找。查找过程N N/2 N/4 N/8不断缩小一半。所以O(logN)5️⃣ O(2^N)典型递归斐波那契。递归结构Fib(N) / \ Fib(N-1) Fib(N-2)递归数量快速增长2^N时间复杂度O(2^N)五、最好、平均、最坏情况很多算法输入不同执行次数不同。例如数组查找数组长度N 查找x最好情况第一次找到1次最坏情况最后找到N次平均情况约N/2次实际开发和面试中通常关注最坏情况复杂度因此数组搜索O(N)六、空间复杂度详解空间复杂度表示算法运行过程中额外占用空间。注意不是统计程序所有内存。而是额外申请的空间数量示例1O(1)int a; int b;固定变量O(1)示例2O(N)动态申请malloc(n*sizeof(int))申请N个空间O(N)Lesson2--时间复杂度空间复杂度.pdfPDF示例3递归空间递归Fac(N)调用N层产生N个栈帧空间复杂度O(N)七、算法复杂度排行榜从优秀到较差O(1) ↓ O(logN) ↓ O(N) ↓ O(NlogN) ↓ O(N²) ↓ O(2^N) ↓ O(N!)一般来说复杂度效率O(1)非常高O(logN)优秀O(N)良好O(N²)数据大时需优化O(2^N)通常不可接受八、总结本文学习了✅ 什么是算法效率✅ 时间复杂度计算方法✅ 大O渐进表示法✅ 常见复杂度分析✅ 最好、平均、最坏情况✅ 空间复杂度计算方法掌握复杂度分析是学习数组链表栈队列树图排序算法的基础。也是程序员面试中的高频考点。推荐阅读数据结构与算法学习路线复杂度分析 ↓ 线性表 ↓ 栈和队列 ↓ 树 ↓ 排序算法 ↓ 图算法 ↓ 算法设计

企业数字化 ERP 产品动态

相关推荐

Linux入门指导

1.利用VMware安装Linux操作系统的详细步骤（图➕文字注解）（1）建立硬件选择创建的虚拟机选择自定义高级输入虚拟机名称并选择创建的位置（2）调整虚拟机硬件（3）选择编辑虚拟机设置并安装… · 2026/9/27 22:57:43

软考系统架构设计师论文 —— 论大模型驱动的软件工程架构及其应用（2）

接前一篇文章：软考系统架构设计师论文 —— 论大模型驱动的软件工程架构及其应用（1）论题随着大模型（Large Language Model，LLM）在自然语言处理、代码生成和智能决策等方面的突破，软件工程正迎来新一轮范式变革。传统软件开发流程以“需求—设计—编码—测试—运维”为… · 2026/9/27 22:57:43

第003篇流程控制 if-else 与 switch——分支逻辑规范写法

摘要：本篇是《Android软件开发面试从入门到精通》第 3 篇，主题为「流程控制 if-else 与 switch——分支逻辑规范写法」。「流程控制 if-else 与 switch——分支逻辑规范写法」属于Java 核心基础阶段的必修内容。概念不难，难的是把原理、代价与边界讲清楚，这正是面试的区分度… · 2026/9/27 22:57:43

STM32智能花盆：闭环自动浇水系统实战设计

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 23:29:48

STM32CubeMX嵌入式开发工具教程：从固件库管理到ADC、SPI、LwIP配置与常见报错排查

WSA玩机必备：ADB连接与设备型号伪装实战指南

Ludusavi 0.31.0 Windows 64位下载：游戏存档备份与恢复说明

Ludusavi 0.31.0 Windows 64位下载官方发行页本文整理 Ludusavi 0.31.0 的Windows 64位压缩包，供需要固定版本的游戏存档备份环境使用。备用入口经草料提示页进入夸克，点击“继续访问”查看文件；登录与下载要求以实际页面为准。文件信息… · 2026/9/27 23:29:48