本文深入探讨了Java中循环的时间复杂度分析，特别是当循环的起始和结束点作为参数传入时。我们解释了在这种情况下，循环的迭代次数直接取决于输入范围的大小（即`high - low + 1`），从而导致其时间复杂度为O(n)。理解算法的“输入规模”是正确评估其效率，特别是区分O(1)和O(n)的关键。
理解时间复杂度
时间复杂度是衡量算法运行时间与输入规模之间关系的一个度量。它通常使用大O符号表示，例如O(1)、O(n)、O(n²)、O(log n)等。大O符号关注的是当输入规模趋于无穷大时，算法运行时间增长的趋势，忽略常数因子和低阶项。
- O(1) - 常数时间复杂度：无论输入规模多大，算法执行的操作次数都是固定的。
- O(n) - 线性时间复杂度：算法执行的操作次数与输入规模成正比。
- O(n²) - 平方时间复杂度：算法执行的操作次数与输入规模的平方成正比。
分析可变边界循环的时间复杂度
考虑以下Java方法：
private static int f (int[] a, int low, int high) {
int res = 0; // 操作1: 初始化
for (int i = low; i <= high; i++) { // 循环控制
res += a[i]; // 操作2: 数组访问和加法
}
return res; // 操作3: 返回
}要分析这个方法的时间复杂度，我们需要识别其核心操作以及这些操作如何随“输入规模”的变化而变化。
立即学习“Java免费学习笔记（深入）”；
- 初始化操作 int res = 0;: 这是一次赋值操作，执行一次，时间复杂度为O(1)。
- 返回操作 return res;: 这也是一次操作，执行一次，时间复杂度为O(1)。
- 循环体内的操作 res += a[i];: 在每一次循环迭代中，都会执行一次数组元素的访问（a[i]）和一次加法操作（res += ...）。这些都是基本操作，每次迭代的时间复杂度为O(1)。
- 循环的迭代次数: 这是关键所在。for (int i = low; i
定义“输入规模”
在这个特定的方法中，虽然传入了一个数组 a，但算法实际处理的元素数量并不是整个数组的长度，而是由 low 和 high 参数决定的子范围。因此，对于这个方法而言，其“输入规模” n 应该定义为 high - low + 1，即循环将执行的次数。
由于循环体内每次迭代都执行O(1)的操作，并且循环总共执行 n 次，所以循环部分的总体时间复杂度是 n * O(1) = O(n)。
将所有部分的复杂度结合起来： 总时间复杂度 = O(1) (初始化) + O(n) (循环) + O(1) (返回) 根据大O符号的规则，我们只保留最高阶项，因此该方法的最终时间复杂度为 O(n)。
示例与辨析
假设有以下调用：
- f(myArray, 0, 9)：此时 low=0, high=9，n = 9 - 0 + 1 = 10。循环执行10次。时间复杂度为O(10)，简化为O(1)（因为10是常数）。
- f(myArray, 0, myArray.length - 1)：此时 low=0, high=myArray.length - 1。如果 myArray.length 是 M，那么 n = M - 1 - 0 + 1 = M。循环执行 M 次。时间复杂度为O(M)，即O(n)，其中 n 代表数组的长度。
- f(myArray, lowParam, highParam)：当 lowParam 和 highParam 是可变的整数参数时，highParam - lowParam + 1 的值会随着输入的不同而变化。我们用 n 来代表这个可变范围的大小。因此，时间复杂度为O(n)。
关键点：判断是O(1)还是O(n)取决于 high - low + 1 这个值是否是常量。如果 high 和 low 始终是固定的数值（例如 0 和 9），那么循环次数是固定的，时间复杂度就是O(1)。但如果 high 和 low 是作为方法参数传入，并且它们的值可以任意变化，那么 high - low + 1 就不再是一个常数，而是与输入相关的变量，此时时间复杂度就是O(n)。
总结
在分析算法的时间复杂度时，核心在于：
- 识别基本操作：确定算法中哪些操作是原子性的，它们的执行时间是常数。
- 确定操作的执行频率：特别是对于循环结构，需要计算循环体的总执行次数。
- 定义“输入规模”：明确哪个变量或参数的变化会影响算法的执行时间。
- 使用大O符号：忽略常数因子和低阶项，表达算法运行时间随输入规模增长的趋势。
对于本例中的 f 方法，由于循环的迭代次数直接取决于传入的 low 和 high 参数所定义的范围大小，而这个范围大小是可变的，因此其时间复杂度为O(n)。
