一文吃透数据结构与算法基础 | 复杂度分析核心详解

一文吃透数据结构与算法基础 | 复杂度分析核心详解前言不管是校招面试、后端开发、前端业务优化还是算法刷题数据结构与算法都是程序员必备底层基本功。很多新手一上来就死磕链表、二叉树、各种排序却跳过基础概念与复杂度分析写出低效代码面试被问复杂度直接卡壳。本文基于核心课堂笔记扩充优化搭配分类图示标记、代码示例、化简规则完整梳理数据结构、算法、时空复杂度全套入门理论适合零基础自学、期末复习、面试速看。一、数据结构核心基础概念1. 五大基础术语层级关系数据数据对象同类数据元素集合数据元素基本处理单元一行记录数据项最小不可分割单元字段数据所有能输入计算机、可被处理的符号总称数字、文本、图片、音频、视频都属于数据。数据元素数据的基本操作单位是数据对象里的独立个体。例学生信息表中的一整条学生记录。数据项数据最小拆分单位无法再细分组成数据元素。例学生记录里的学号、姓名、年龄、班级。数据对象性质相同的数据元素的集合是数据的子集。例全校所有学生、1~100 全部整数。数据结构相互存在特定关系的数据元素的集合分为两大维度逻辑结构数据元素之间抽象关系物理结构数据在内存真实存储形式2. 逻辑结构4大类仅描述元素抽象关系和内存存放无关。逻辑结构集合结构线性结构树形结构图形结构类型关系特征常见结构集合结构仅同属一个集合元素无任何关联哈希集合、无序集合。线性结构一对一有唯一首、尾节点数组、链表、栈、队列、字符串。树形结构一对多分层父子关系二叉树、堆、红黑树。图形结构多对多网状连通有向图、无向图、拓扑图。3. 物理存储结构2大类逻辑结构需要物理载体落地决定内存布局。物理存储结构顺序存储链式存储① 顺序存储结构内存地址连续整块存放元素。[10][20][30][40] 连续地址优点支持下标随机访问查询速度快。缺点插入/删除需要移动大量元素扩容成本高。代表数组int arr[100];。② 链式存储结构数据分散在零散内存中依靠指针保存下一个节点的地址[10 | *next] → [20 | *next] → [30 | null]优点插入、删除仅修改指针无需移动元素缺点不支持随机访问遍历需要逐个跳转代表单链表、双向链表二、算法完整认知1. 数据结构与算法关系数据结构 数据怎么存算法 数据怎么操作二者不可分割合适的数据结构能极大优化算法效率。经典对比案例求 1~100 累加和方式 1循环遍历暴力算法intsum0;for(inti1;i100;i){sumi;}执行次数100 次依赖数据规模方式 2高斯等差数列公式数学优化算法intsum(1100)*100/2;执行次数固定 3 次和数据规模无关两种方案实现同一需求但执行效率差距巨大这就是复杂度分析的意义。2. 算法定义算法是解决特定问题求解步骤的有限指令序列每条指令对应一个或多个计算机操作。重点不存在通用算法能解决所有问题不同业务场景需要针对性设计算法。3. 算法五大硬性特性缺一不可输入0 个或多个输入数据输出至少 1 个输出算法必须产出结果有穷性有限步骤内自动结束无无限死循环执行时长可控确定性每一步含义唯一、无歧义相同输入一定得到相同输出可行性每一步操作都能通过有限次运算完成不存在无法执行的步骤4. 优质算法四大设计标准正确性合法输入、边界值、极值都能输出正确结果可读性逻辑清晰、注释规范拒绝晦涩炫技代码方便团队维护健壮性兼容非法输入空值、负数、越界参数不会直接程序崩溃时间效率高 存储占用低运行速度快额外内存开销小三、时间复杂度衡量算法运行快慢1. 核心原理时间复杂度 ≠ 程序真实运行毫秒数用于描述执行次数随数据规模 N 增长的变化趋势计算公式程序总执行时间单条指令耗时×指令总执行次数程序总执行时间 单条指令耗时 × 指令总执行次数程序总执行时间单条指令耗时×指令总执行次数硬件单条指令耗时固定因此只需要统计循环、操作执行次数。2. 大 O 渐进表示法化简三大规则统一简化复杂度函数T(N)T(N)T(N)只关注增长趋势只保留最高阶项丢弃全部低阶项最高阶项系数不为 1 时直接去掉系数表达式无 N 相关项统一用常数O(1)O(1)O(1)代替代码示例化简演示示例 1T(N)3N25N20T(N) 3N^2 5N 20T(N)3N25N20最高阶N2N^2N2去掉系数3 →O(N2)O(N^2)O(N2)// 两层嵌套循环复杂度 O(N²)for(inti0;in;i){for(intj0;jn;j){// 单次操作}}示例 2T(N)1000T(N) 1000T(N)1000无N项 →O(1)O(1)O(1)// 固定次数执行和n无关inta10;intb20;intcab;示例 3T(N)4N100T(N) 4N 100T(N)4N100最高阶N去掉系数4 →O(N)O(N)O(N)// 单层循环复杂度 O(N)for(inti0;in;i){}常见复杂度排序由快到慢O(1)O(log⁡N)O(N)O(Nlog⁡N)O(N2)O(2N)O(1) O(\log N) O(N) O(N \log N) O(N^2) O(2^N)O(1)O(logN)O(N)O(NlogN)O(N2)O(2N)四、空间复杂度衡量算法内存开销1. 核心概念空间复杂度统计算法运行时额外动态开辟的临时空间不包含原始输入数据占用的内存同样使用大 O 表示法。统计对象临时变量、动态数组、链表、递归额外栈等。重要注意点函数默认调用栈空间在编译阶段已确定不计入空间复杂度仅统计运行时手动显式申请的额外内存。代码示例示例 1常数空间 O(1)仅定义固定数量临时变量无动态内存。intfunc(intn){inta1;intb2;returnab;}示例 2线性空间 O(N)根据输入规模 n 动态创建数组额外空间随 N 变化intfunc(intn){// 动态开辟长度n的数组int*arr(int*)malloc(sizeof(int)*n);returnarr[0];}五、核心知识点总结数据结构与算法数据结构基础五大术语数据/数据对象/数据元素/数据项逻辑结构集合/线性/树/图物理结构顺序存储/链式存储算法理论五大特性输入输出/有穷性/确定性/可行性四大设计要求正确/可读/健壮/低时空开销复杂度分析时间复杂度看执行次数衡量运行速度空间复杂度看额外动态内存衡量内存开销1数据结构分为逻辑关系和物理存储两层4 类逻辑、2 种存储是底层根基算法有 5 条硬性约束工业开发中优先保证正确性、可读性再优化时空效率时间复杂度只关心操作次数增长趋势不看真实运行时间空间复杂度只统计运行时手动开辟的额外内存固定栈空间不参与计算大 O 渐进表示法是行业统一标准忽略常数、低阶项只保留最高阶增长趋势。结尾掌握这套底层理论后再学习链表、树、排序、查找等具体结构与算法才能精准判断不同写法的性能优劣写出高效、规范的工程代码同时轻松应对面试复杂度分析提问。