嵌套for循环的运行时间如何用Big O、Theta、Omega计算？

首先给出你提供的代码块：

for(i=1; i<n; i++) {
    for(j=1; j<n; j++) {
       //some piece of code
    }
}

默认前提：内层注释处的代码是不随n变化的固定耗时操作，即单次执行复杂度为O(1)。

执行次数计算 #

• 外层for循环的变量i从1遍历到n-1，总共执行n-1次
• 每执行1次外层循环，内层for循环的变量j同样从1遍历到n-1，单次外层循环对应n-1次内层执行
• 总操作次数为(n-1)*(n-1) = n² - 2n +1

三类复杂度判定 #

当n足够大时，低阶项（-2n）和常数项（+1）对整体量级的影响可以忽略，据此得出三类复杂度：

• O(n²)（大O上界）：代表代码运行时间的增长速度不会超过n²的量级，是最坏情况的增长上限
• Ω(n²)（大Omega下界）：代表代码运行时间的增长速度不会慢于n²的量级，是最好情况的增长下限
• Θ(n²)（大Theta紧界）：当上界和下界的量级一致时，即可得到紧界，代表代码运行时间的实际增长速率和n²属于同一量级

注：如果内层代码的耗时随n变化，需要把内层代码的复杂度乘以当前的外层循环次数重新计算总复杂度。

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