algorithm - 如果循环体中什么都没有发生，那么 for 循环的复杂度是多少

Question

代码:

            int c = 0;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    c = i * j;
                }
            }

时间复杂度:O(n²)

现在下面代码的复杂度是多少:

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    //c = i * j;
                    // nothing is happening inside the loop
                }
            }

复杂度是否与上述相同(O(n²))或其他？

Answer 1

理论上 - 是的，因为仍然存在增加 i 和 j 的问题，这仍然需要发生，并将它们与每次迭代中的最终值进行比较。

但是 - 编译器可能会优化它以在恒定时间内完成，并且只需设置 i 和 j 的 post 值。