计算含if判断语句的嵌套循环的Big O时间复杂度

你提供的180度旋转方阵的代码片段如下：

System.out.println("\nHasil:");
for (i= arr.length-1; i>=0; i--) {
    System.out.print("[");
    for (j= arr.length-1; j>=0; j--){
        System.out.print(arr[i][j]);
        if (j != 0) {
            System.out.print(",");
        }
    }
    System.out.println("]");
}

时间复杂度结论 #

这段代码的时间复杂度为O(n²)，其中n为输入二维方阵的边长。

计算逻辑说明 #

• 大O时间复杂度衡量的是算法运行时间随输入规模增长的渐近上界，仅关注最高阶的增长趋势，常数系数、低阶运算、单次常数时间的操作都不会改变复杂度量级。
• 首先统计循环的总执行次数：
  • 外层循环逐行遍历数组，总共执行n次
  • 每一轮外层循环中，内层循环会遍历当前行的所有n个元素，两层循环累计执行n * n = n²次内层循环体
• 内层循环中的if判断属于常数时间操作，无论判断是否成立，后续执行的打印操作也都是常数时间，不会引入随n增长的额外运算量。即便if每次都命中，总操作数也只是n²乘以固定的常数系数，大O表示法会省略该常数系数，因此不会影响整体的时间复杂度量级。

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