大O表达式用于描述算法的时间复杂度和空间复杂度，反映算法执行效率随输入规模增长的趋势，在JAVA中进行算法分析时，掌握其计算和简化方法是优化代码的基础。
大O表达式的核心概念
大O表达式关注的是算法执行次数随输入规模n增长的最坏情况趋势，忽略常数项、低阶项和系数，只保留增长最快的项。常见的大O复杂度从低到高依次为O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)等。
JAVA中计算大O表达式的步骤
1. 分析代码执行次数
首先统计代码中核心操作（如循环、赋值、判断）的执行次数，再将其表示为输入规模n的函数。
场景一：单层循环
如下代码中，循环体执行n次，核心操作次数为n，因此时间复杂度为O(n)。
public class TimeComplexityDemo {
// 单层循环，遍历数组元素
public static void printArray(int[] arr) {
int n = arr.length; // 输入规模n为数组长度
// 循环执行n次，每次执行一次打印操作
for (int i = 0; i < n; i++) {
System.out.println(arr[i]);
}
}
}场景二：嵌套循环
嵌套循环的执行次数是各层循环次数的乘积，如下代码中外层循环n次，内层循环n次，总执行次数为n*n，时间复杂度为O(n²)。
public class NestedLoopDemo {
// 嵌套循环，计算二维数组元素和
public static int sumMatrix(int[][] matrix) {
int n = matrix.length; // 矩阵行数，输入规模n
int sum = 0;
// 外层循环n次
for (int i = 0; i < n; i++) {
// 内层循环n次
for (int j = 0; j < n; j++) {
sum += matrix[i][j];
}
}
return sum;
}
}场景三：递归场景
递归算法的大O计算需要分析递归调用的次数和每次递归的操作次数，如下斐波那契递归实现，每次递归会调用两次自身，总调用次数呈指数增长，时间复杂度为O(2ⁿ)。
public class RecursionDemo {
// 递归实现斐波那契数列
public static int fibonacci(int n) {
// 基线条件
if (n <= 1) {
return n;
}
// 每次递归调用两次自身，总调用次数指数增长
return fibonacci(n - 1) + fibonacci(n - 2);
}
}2. 简化大O表达式
得到执行次数的函数后，按照以下规则简化：
- 忽略常数项：例如O(2n + 3)简化为O(n)，因为常数项对增长趋势影响可忽略
- 忽略低阶项：例如O(n² + n + 5)简化为O(n²)，低阶项增长远慢于最高阶项
- 忽略系数：例如O(3n log n)简化为O(n log n)，系数不影响增长趋势
空间复杂度的大O计算
空间复杂度关注算法运行时额外占用的内存空间随输入规模的增长趋势，计算方式和时间复杂度类似，只统计额外申请的变量、数组等空间。
如下代码中，只申请了固定数量的变量，额外空间不随输入规模n变化，空间复杂度为O(1)。
public class SpaceComplexityDemo {
// 计算数组最大值，额外空间为固定变量
public static int findMax(int[] arr) {
int n = arr.length;
int max = arr[0]; // 固定变量
for (int i = 1; i < n; i++) { // 固定变量i
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
}如果申请了和输入规模n成正比的额外空间，例如新建长度为n的数组，空间复杂度则为O(n)。
常见误区说明
很多开发者会误将代码行数等同于复杂度，实际上大O关注的是增长趋势，而非具体执行次数。另外，不同输入规模下同一算法的大O可能不同，例如某些排序算法在已排序数组上的时间复杂度会低于最坏情况，但大O通常描述最坏情况的复杂度。