目录一、为什么要关心算法效率如何衡量一个算法的好坏二、时间复杂度算法到底跑了多久2.1 时间复杂度的本质2.2 大O渐进表示法2.3 最好、平均、最坏情况2.4 常见时间复杂度计算实战实例1单层循环 常数操作实例2两个未知数的双层循环实例3常数次操作实例4冒泡排序实例5二分查找实例6阶乘递归实例7斐波那契递归经典反面教材三、空间复杂度算法占了多少内存3.1 空间复杂度的本质3.2 空间复杂度计算实战实例1冒泡排序实例2斐波那契数列非递归版本实例3阶乘递归四、时间复杂度与空间复杂度的权衡五、常见时间复杂度对比六、如何提升算法效率的分析能力七、写在最后写在前面本文是基于数据结构中关于时间复杂度和空间复杂度章节的学习整理结合了个人理解和代码实践。文中所有示例均经过重新编写和验证旨在帮助初学者建立对算法效率的正确认知。如需深入学习建议配合原版教材或官方文档使用。一、为什么要关心算法效率还记得我们之前聊过的Java集合框架吗ArrayList和LinkedList同样是List接口的实现类为什么在不同场景下性能差异巨大这背后就是算法效率在起作用。举个最简单的例子假设你要在一个包含100万个元素的列表中查找某个值。顺序查找运气不好时需要比较100万次二分查找最多只需要比较20次这就是算法效率带来的差距——同样的功能不同的实现方式性能可能天差地别。如何衡量一个算法的好坏我们先来看一个经典的斐波那契数列递归实现public static long fib(int N) { if (N 3) { return 1; } return fib(N - 1) fib(N - 2); }这段代码看起来简洁优雅但当你尝试计算fib(50)时会发现它慢得令人崩溃。为什么因为它做了大量的重复计算。衡量算法好坏的两个核心指标就是时间复杂度和空间复杂度。二、时间复杂度算法到底跑了多久2.1 时间复杂度的本质时间复杂度并不是指算法实际的运行时间因为不同机器、不同语言、不同输入都会影响而是算法中基本操作的执行次数与输入规模之间的关系。简单来说输入规模越大算法要做的操作越多这个多多少就是时间复杂度关心的核心问题。2.2 大O渐进表示法在实际工程中我们并不需要精确计算算法的执行次数而是关注其增长趋势。这就是大O表示法的作用。推导大O阶的三个原则用常数1取代运行时间中的所有加法常数只保留最高阶项如果最高阶项存在且系数不为1去掉系数举个例子假设一个算法的基本操作执行次数为F(N)N^22N10根据大O表示法当N很大时2N10相对于 N^2可以忽略不计所以时间复杂度为 O(N^2)2.3 最好、平均、最坏情况同一个算法在不同输入下的表现可能完全不同。以在数组中查找某个值为例最好情况第一个就是要找的元素1次找到 → O(1)最坏情况最后一个才是要找的元素N次找到 → O(N)在实际开发中我们通常关注最坏情况因为这代表了算法的性能下限。2.4 常见时间复杂度计算实战实例1单层循环 常数操作void func2(int N) { int count 0; // 循环2N次 for (int k 0; k 2 * N; k) { count; } // 常数次操作 int M 10; while ((M--) 0) { count; } System.out.println(count); }分析基本操作执行了2N 10次根据大O表示法时间复杂度为O(N)。实例2两个未知数的双层循环void func3(int N, int M) { int count 0; for (int k 0; k M; k) { count; } for (int k 0; k N; k) { count; } }分析执行了M N次两个未知数无法确定谁更大时间复杂度为O(M N)。实例3常数次操作void func4() { int count 0; for (int k 0; k 100; k) { count; } System.out.println(count); }分析无论输入规模多大永远执行100次时间复杂度为O(1)。实例4冒泡排序void bubbleSort(int[] array) { for (int end array.length; end 0; end--) { boolean sorted true; for (int i 1; i end; i) { if (array[i - 1] array[i]) { swap(array, i - 1, i); sorted false; } } if (sorted) { break; } } }分析最好情况数组已经有序执行N次 → O(N)最坏情况数组完全逆序执行N*(N-1)/2次 → O(N²)实际中我们关注最坏情况所以时间复杂度为O(N²)。实例5二分查找int binarySearch(int[] array, int value) { int begin 0; int end array.length - 1; while (begin end) { int mid begin ((end - begin) / 2); if (array[mid] value) { begin mid 1; } else if (array[mid] value) { end mid - 1; } else { return mid; } } return -1; }分析每次查找都将范围缩小一半经过log₂N次查找后找到目标。时间复杂度为O(log N)。小技巧你可以把二分查找想象成猜数字游戏——每次猜中间值然后根据提示大了或小了排除掉一半的数字。这样理解起来会更直观。实例6阶乘递归long factorial(int N) { return N 2 ? N : factorial(N - 1) * N; }分析递归调用了N次每次执行常数操作。时间复杂度为O(N)。实例7斐波那契递归经典反面教材int fibonacci(int N) { return N 2 ? N : fibonacci(N - 1) fibonacci(N - 2); }分析这是一个指数级的递归调用每次调用会产生两个新的调用形成一棵深度为N的二叉树。总调用次数约为 2^N次时间复杂度为O(2^N)。这也是为什么用递归计算fib(50)会慢到让人怀疑人生的原因——它需要执行大约 250次操作三、空间复杂度算法占了多少内存3.1 空间复杂度的本质空间复杂度衡量的是算法在运行过程中临时占用的存储空间大小。注意这里说的是临时——即除了输入数据本身之外额外需要的空间。在计算机发展早期内存非常珍贵空间复杂度曾是重中之重。但如今随着硬件成本的降低我们通常更关注时间复杂度。不过在某些场景下如嵌入式系统、移动设备空间复杂度依然很重要。3.2 空间复杂度计算实战实例1冒泡排序void bubbleSort(int[] array) { for (int end array.length; end 0; end--) { boolean sorted true; // 1个变量 for (int i 1; i end; i) { if (array[i - 1] array[i]) { swap(array, i - 1, i); sorted false; } } if (sorted) { break; } } }分析只使用了常数个额外变量end、sorted、i等不随输入规模变化。空间复杂度为O(1)。实例2斐波那契数列非递归版本int[] fibonacci(int n) { long[] fibArray new long[n 1]; fibArray[0] 0; fibArray[1] 1; for (int i 2; i n; i) { fibArray[i] fibArray[i - 1] fibArray[i - 2]; } return fibArray; }分析创建了一个大小为n1的数组空间随输入规模线性增长。空间复杂度为O(N)。实例3阶乘递归long factorial(int N) { return N 2 ? N : factorial(N - 1) * N; }分析递归调用N次每次调用会在栈上创建一个栈帧每个栈帧占用常数空间。总共占用N个栈帧空间复杂度为O(N)。四、时间复杂度与空间复杂度的权衡在算法设计中时间和空间往往是一对矛盾体。有时候我们可以用空间换时间也可以用时间换空间。典型例子斐波那契数列递归版本时间复杂度 O(2^N)空间复杂度 O(N)迭代版本时间复杂度 O(N)空间复杂度 O(1)显然迭代版本无论在时间还是空间上都优于递归版本。这也告诉我们写代码时不要盲目追求优雅的递归要考虑实际性能。五、常见时间复杂度对比时间复杂度名称举例性能评价O(1)常数阶数组随机访问⭐⭐⭐⭐⭐O(log N)对数阶二分查找⭐⭐⭐⭐O(N)线性阶顺序查找⭐⭐⭐O(N log N)线性对数阶归并排序⭐⭐⭐O(N²)平方阶冒泡排序⭐⭐O(2^N)指数阶斐波那契递归⭐六、如何提升算法效率的分析能力多动手画图特别是递归调用、循环嵌套这种抽象的结构画图能让思路清晰很多刻意练习在LeetCode或牛客网上做题时养成先分析时间空间复杂度的习惯阅读优秀源码JDK源码中有大量精妙的实现值得反复品味总结归纳遇到新的算法模式时记下来并与已知的模式做对比七、写在最后时间复杂度和空间复杂度是算法分析的基石也是面试中绕不开的话题。理解它们不仅能帮你在面试中脱颖而出更能让你在日常开发中写出更高效的代码。下一篇文章我们将把这些知识应用到集合框架的源码分析中看看ArrayList和LinkedList各自的性能特点是如何由它们的底层数据结构决定的。如果你觉得这篇文章有帮助欢迎点赞收藏。有任何疑问欢迎在评论区交流探讨注本文为个人学习总结文中示例均为独立编写。建议读者在学习过程中结合实际代码运行验证加深理解。