欢迎来到本系列数据结构第一篇很多初学编程的朋友会疑惑日常业务开发只写 CRUD为什么还要钻研数据结构与算法校招笔试算法题是筛选门槛面试深挖底层存储原理上线后海量数据下系统性能更是直接由算法效率决定足以看出它的核心地位。本文先通俗讲清数据结构、算法的基础概念梳理二者在求职、工作中的实用价值分享高效学习路径与优质学习资源最后重点拆解时间、空间复杂度这一核心评判标准带你看懂如何衡量代码运行效率。全文避开晦涩理论结合实例通俗讲解零基础也能轻松读懂为后续顺序表、链表等内容打好理论基础。一、数据结构前言1. 什么是数据结构数据结构Data Structure是计算机存储、组织数据的方式。简单来说它研究的是数据元素之间的关系以及如何在计算机中高效地保存和操作这些数据。常见的数据结构包括线性结构数组、链表、栈、队列树形结构二叉树、AVL树、红黑树、堆图状结构有向图、无向图散列结构哈希表一句话理解数据结构 数据 数据之间的关系。2. 什么是算法算法Algorithm是解决特定问题的清晰、有限的步骤序列。它具有以下五个基本特性特性说明输入有零个或多个外部输入输出至少产生一个输出有穷性有限步骤内必须结束确定性每一步含义明确无歧义可行性每一步都能通过基本操作实现数据结构是算法的载体算法是对数据结构的操作。二者密不可分——同样的问题选择不同的数据结构算法的效率可能天差地别。3. 数据结构和算法的重要性1.在校园招聘的笔试中几乎所有互联网公司的技术笔试都会考察算法能力常见题型包括数组、链表操作反转链表、合并有序数组等排序与查找快排、二分查找动态规划、贪心算法树与图的遍历笔试通常在 LeetCode / 牛客网等 OJ 平台进行直接考察代码的正确性和时间/空间复杂度。2.在校园招聘的面试中面试环节中算法题往往是技术面的核心环节面试官通过手撕代码考察逻辑思维能力代码基本功边界条件处理、代码风格复杂度分析能力是否能主动优化解法沟通表达能力能否清晰讲解思路3.在未来的工作中工作中虽然不会天天手撕算法但数据结构与算法的思维会渗透到日常开发的方方面面选择合适的容器如用HashMap还是TreeMap直接影响系统性能数据库索引底层就是 B 树高并发场景下的限流、缓存淘汰LRU都是经典算法应用排查性能瓶颈时复杂度分析能力是基本功4. 如何学好数据结构和算法打好基础先吃透数组、链表、栈、队列这些基础结构不要一上来就啃图论、动态规划。手写代码而不是只看算法是练出来的看懂和写出来是两回事建议每个知识点都亲手实现一遍。画图辅助理解链表操作、树的遍历强烈建议配合画图尤其是指针操作类问题。刷题要总结归类按专题刷题如先专攻链表再专攻二叉树做完题要总结同类题的解题套路。重视复杂度分析每写完一道题习惯性分析一下时间复杂度和空间复杂度这是本文 Lesson2 的重点。保持节奏循序渐进数据结构与算法不是短期冲刺能拿下的建议保持每天固定的学习/刷题量。5. 数据结构和算法书籍及资料推荐资料适合人群《数据结构C语言版》严蔚敏国内高校教材体系完整适合系统学习《大话数据结构》入门友好讲解通俗适合零基础《算法导论》进阶必读理论深入适合考研/深入研究《剑指Offer》面试向题目贴近国内大厂真题LeetCode / 牛客网在线刷题平台配合专题练习效果最佳《算法第4版》Sedgewick讲解直观代码规范适合配合视频学习二、算法的时间复杂度和空间复杂度本节目标理解为什么需要复杂度分析掌握大O表示法的推导方法能够独立计算常见算法的时间复杂度和空间复杂度了解复杂度在校招笔试面试中的考察方式1. 算法效率1.1 如何衡量一个算法的好坏同一个问题可能有多种解法比如求斐波那契数列既可以用递归也可以用循环。如何评价哪种算法更好主要从两个维度衡量时间效率算法执行所耗费的时间空间效率算法执行所占用的额外存储空间理论上可以通过事后统计法跑代码计时来比较但这种方法受硬件、编译器、数据规模等因素影响极大不具备通用性和可比性。因此业界普遍采用事前估算法——即通过分析算法本身的操作次数增长趋势来评估效率这就是复杂度分析。1.2 算法的复杂度复杂度分为两类时间复杂度衡量算法执行时间随输入规模增长的变化趋势空间复杂度衡量算法执行过程中额外占用存储空间随输入规模增长的变化趋势复杂度关注的不是具体运行了多少毫秒而是增长趋势——当输入规模 n 趋于无穷大时算法的性能表现如何。1.3 复杂度在校招中的考察在校招笔试/面试中复杂度分析几乎是标配问题面试官在你写完代码后几乎必问一句这个算法的时间复杂度是多少能不能优化OJ 平台对提交代码有时间限制和内存限制复杂度不达标会直接超时TLE或超内存MLE很多题目的难度其实就体现在能否把暴力解法的复杂度降下来例如从 O(n²) 优化到 O(n log n)2. 时间复杂度2.1 时间复杂度的概念时间复杂度定义为算法中基本操作的执行次数是关于问题规模 n 的一个函数记作 T(n)。例如下面这段代码void func(int n) { int count 0; for (int i 0; i n; i) { for (int j 0; j n; j) { count; } } }内层count语句的执行次数是 n × n n²所以 T(n) n²。2.2 大O的渐进表示法严格计算 T(n) 的精确表达式往往很繁琐也没有必要。实际中我们只关心当 n 趋于无穷大时T(n) 的增长趋势这就是大O渐进表示法Big O Notation。推导大O阶的方法用常数 1 取代运行时间中的所有加法常数只保留最高阶项去掉最高阶项的系数例如T(n) 2n² 3n 10推导过程保留最高阶项2n²去掉系数n²结果O(n²)常见的大O阶从低到高O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ) O(n!)O(1)常数阶如数组随机访问O(log n)对数阶如二分查找O(n)线性阶如遍历数组O(n log n)如快速排序、归并排序O(n²)平方阶如冒泡排序、插入排序O(2ⁿ)指数阶如未剪枝的递归斐波那契O(n!)阶乘阶如全排列补充说明如果算法中存在多个不同数量级的输入比如两个字符串长度 m 和 n不能简单合并为一个 n应分别表示如 O(m n)。2.3 常见时间复杂度计算举例例1顺序结构O(1)int sum(int a, int b) { return a b; }只有常数次操作复杂度为 O(1)。例2单层循环O(n)void func(int n) { for (int i 0; i n; i) { printf(%d\n, i); } }循环执行 n 次复杂度为 O(n)。例3双层循环O(n²)void bubbleSort(int arr[], int n) { for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } }外层 n 次内层平均 n/2 次总次数约为 n²/2去掉系数后为 O(n²)。这是经典的冒泡排序。例4折半查找O(log n)int binarySearch(int arr[], int n, int target) { int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) return mid; else if (arr[mid] target) left mid 1; else right mid - 1; } return -1; }每次查找范围减半执行次数约为 log₂n复杂度为 O(log n)。例5递归求阶乘O(n)​long factorial(int n) { if (n 1) return 1; return n * factorial(n - 1); }递归调用 n 次每次做常数次操作复杂度为 O(n)。例6递归斐波那契O(2ⁿ)int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); }未使用记忆化会产生大量重复计算调用次数呈指数级增长复杂度为 O(2ⁿ)。这也是面试中的经典如何优化考点优化后动态规划/记忆化可降到 O(n)。3. 空间复杂度空间复杂度是对算法在运行过程中临时占用存储空间大小的度量同样用大O渐进表示法表示。注意空间复杂度衡量的是额外开辟的空间不包括输入数据本身占用的空间。例1O(1) 空间复杂度void bubbleSort(int arr[], int n) { for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; // 只使用了常数个额外变量 arr[j] arr[j 1]; arr[j 1] temp; } } } }无论 n 多大只用到了temp这一个额外变量空间复杂度为 O(1)。例2O(n) 空间复杂度long* fibonacci(int n) { long* arr (long*)malloc((n 1) * sizeof(long)); // 开辟了 n1 大小的数组 arr[0] 0; arr[1] 1; for (int i 2; i n; i) { arr[i] arr[i - 1] arr[i - 2]; } return arr; }额外开辟了大小为 n 的数组空间复杂度为 O(n)。例3递归带来的 O(n) 空间复杂度long factorial(int n) { if (n 1) return 1; return n * factorial(n - 1); }虽然没有显式开辟数组但递归调用会占用函数调用栈空间每次递归调用都会压入一个栈帧深度为 n因此空间复杂度为 O(n)。易错点很多同学容易忽略递归的栈开销误以为没有malloc/new就是 O(1) 空间这是笔试中的常见陷阱。4. 常见复杂度对比复杂度名称典型算法n1000时相对耗时O(1)常数阶哈希表查找、数组索引极快O(log n)对数阶二分查找很快约10次操作O(n)线性阶遍历数组、线性查找快1000次操作O(n log n)线性对数阶快速排序、归并排序、堆排序较快约10000次操作O(n²)平方阶冒泡排序、插入排序、选择排序一般100万次操作O(n³)立方阶三重循环矩阵乘法较慢10亿次操作O(2ⁿ)指数阶未优化的递归、子集枚举极慢n稍大即不可用O(n!)阶乘阶全排列、旅行商问题暴力解不可用增长曲线直观感受n 从小到大耗时增长速度选择数据结构和算法时优先考虑复杂度更低的方案尤其是当输入规模 n 可能很大时如 n 10^5O(n²) 及以上的算法很可能会超时。5. 复杂度的OJ练习建议按以下顺序在 LeetCode / 牛客网上进行专项练习巩固复杂度分析能力基础练习实现并对比冒泡排序、选择排序、插入排序手动推导各自复杂度二分查找专题LeetCode 704二分查找、35搜索插入位置递归复杂度练习LeetCode 509斐波那契数—— 分别用暴力递归和记忆化实现对比复杂度差异复杂度优化练习LeetCode 1两数之和—— 从暴力 O(n²) 优化到哈希表 O(n)排序进阶牛客网排序专题 —— 实现快速排序、归并排序理解 O(n log n) 的来源练习技巧每做完一道题强制自己写一句时间复杂度O(?)空间复杂度O(?)并说明推导理由坚持下来复杂度分析能力会有明显提升。总结数据结构是数据的组织方式算法是解决问题的步骤二者相辅相成复杂度分析是评价算法优劣的核心工具比跑代码计时更通用、更本质时间复杂度关注基本操作次数随 n 的增长趋势空间复杂度关注额外空间占用随 n 的增长趋势注意递归的栈空间开销校招笔试面试中复杂度分析能力和刷题量同样重要建议养成写完代码就分析复杂度的习惯下一节将继续讲解常见线性数据结构顺序表、链表的实现与复杂度分析敬请期待。