嵌套循环时间复杂度疑问：为何是Θ(N²)而非Θ(N(N-2))？

先算清楚这个嵌套循环的总执行次数：外层循环for 0 <= i < N会跑N次，内层循环for 1 <= j < N-1每次会跑(N-2)次，所以总次数是N*(N-2) = N² - 2N。

那为什么时间复杂度是Θ(N²)而不是Θ(N(N-2))？核心在于Θ符号的定义——它描述的是算法在N趋近于无穷大时的渐近增长趋势，只会保留最高阶的主导项，忽略低阶项和常数系数。

具体来说：

• N(N-2)展开后是N²-2N，其中N²是最高阶项，-2N是低阶项。当N变得极大时，低阶项对整体增长的影响会被高阶项完全覆盖，所以可以直接忽略。
• 从渐近等价的角度看，Θ(N-2)和Θ(N)是完全一样的——因为N-2和N的增长速率是线性等价的，只差一个常数偏移，不影响渐近阶。外层循环是Θ(N)，内层是Θ(N)，嵌套起来自然就是Θ(N*N)=Θ(N²)。

至于“计算时间复杂度时要不要考虑循环上下界”——要考虑，但不是看精确的数值，而是看上下界对应的增长阶。比如：

• 如果内层循环是固定次数（比如for j=1 to 10），那内层是Θ(1)，整体复杂度就是Θ(N)；
• 如果内层循环次数是对数级（比如for j=1 to logN），那整体是Θ(NlogN)；
• 但只要内层循环的执行次数是随N线性增长的（哪怕是N-2、N/2这种），它的渐近阶都是Θ(N)，嵌套后就是Θ(N²)。

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