Java基础时间复杂度疑问：区间数组求和方法的复杂度判定

这个方法的时间复杂度是O(n)，其中n代表high - low + 1，也就是循环实际执行的次数。

时间复杂度的核心是衡量算法执行步骤数随输入规模增长的变化趋势：

• O(1)表示无论输入规模多大，执行步骤数始终固定，和输入无关；
• 你的代码里，for循环的执行次数完全由参数low和high决定：循环从low开始，到high结束，一共会执行high - low + 1次加法操作。当high和low的差值越大（也就是要累加的元素越多），循环执行的次数就越多，执行步骤数和这个差值呈线性正相关，完全符合O(n)的特征。

比如当low=0、high=99时，循环执行100次；如果high=999，循环就会执行1000次——步骤数随处理的元素数量线性增长，显然不是固定次数的O(1)。

内容的提问来源于stack exchange，提问作者Dima Tkachuk