什么是时间复杂度、什么是空间复杂度？

在 Java 算法以及所有计算机科学领域中时间复杂度和空间复杂度是衡量算法效率的两个核心指标。它们通常使用大 O 表示法Big O Notation来描述。简单来说它们衡量的是当数据规模通常用 nn 表示增大时算法的执行时间或内存消耗是如何变化的。1. 时间复杂度 (Time Complexity)定义时间复杂度并不是指代码运行的“绝对时间”比如 2 秒或 5 毫秒而是指算法中基本操作的执行次数与数据规模 nn 之间的增长关系。在 Java 中如何看看循环单层循环通常是 O(n)O(n) 嵌套循环通常是 O(n2)O(n2) 。看递归需要结合递归树的深度和每层的操作次数。看 Java APIArrayList.get(i)是 O(1)O(1) 而ArrayList.remove(0)是 O(n)O(n) 因为后续元素都要往前挪。常见的时间复杂度从快到慢O(1)O(1)常数时间无论数据多少执行时间不变。例如数组按索引取值。O(log⁡n)O(logn)对数时间每次操作数据量减半。例如二分查找。O(n)O(n)线性时间执行次数与数据量成正比。例如遍历一次数组。O(nlog⁡n)O(nlogn)线性对数时间高效排序算法的典型复杂度。例如Java 的Arrays.sort()双轴快排/归并。O(n2)O(n2)平方时间双重嵌套循环。例如冒泡排序、简单的两数之和暴力解法。2. 空间复杂度 (Space Complexity)定义空间复杂度是指算法在运行过程中临时占用存储空间的大小与数据规模 nn 之间的增长关系。⚠️ Java 中的关键注意点在 Java 中空间复杂度主要关注额外空间Auxiliary Space即除了输入数据本身占用的内存外算法还需要多少额外内存。常见场景O(1)O(1)常数空间只用了几个固定的变量没有创建新的集合或大数组。// 无论 n 多大只用了一个 sum 变量 int sum 0; for(int i0; in; i) sum i;O(n)O(n)线性空间创建了一个与输入规模相关的新数组或集合。// 创建了一个长度为 n 的新数组 int[] copy new int[n];O(n)O(n)递归栈空间Java 的递归调用会占用栈内存。如果递归深度为 nn 空间复杂度就是 O(n)O(n) 。// 递归 n 次栈帧占用 O(n) 空间 void recursion(int n) { if(n 0) return; recursion(n-1); }3. 一个直观的 Java 例子假设我们要计算 12...n12...n 方案 A循环long sum 0; // O(1) 空间 for (int i 1; i n; i) { // 循环 n 次 sum i; // 基本操作 }时间复杂度O(n)O(n)空间复杂度O(1)O(1)方案 B数学公式return n * (n 1) / 2; // 只做一次乘法和除法时间复杂度O(1)O(1)空间复杂度O(1)O(1)总结指标关注点核心问题时间复杂度CPU 执行次数数据量翻倍代码要多跑多少倍空间复杂度内存额外占用数据量翻倍需要多申请多少内存在实际开发中我们通常追求时间换空间或空间换时间的平衡。例如用HashMap缓存结果增加 O(n)O(n) 空间来将查找时间从 O(n)O(n) 降到 O(1)O(1) 这就是典型的空间换时间。