java - 我应该如何估计 Java 中 for 循环的时间函数 (T(N))？

Question

我对如何估计 Java 中 for 循环的时间函数 (T(N)) 感到困惑。如果我能看到一个例子，我就能掌握它的窍门，但我似乎找不到我要找的东西。估计这个的最佳方法是什么？

for(int x=0; x<N; x=x+2){
    for(int y=x; y<N; y++){
        System.out.println("!");
    }
}

Answer 1

第一个循环执行 N/2 次，第二个循环也执行 N/2 次。因此，您总共有 (N/2) * (N/2) 这是 O(n*n) 因为在时间复杂度计算中可以安全地排除常量。