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仍然需要发生的问题，并将它们与每次迭代中的最终值进行比较。

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

Answer 2

两种复杂度都是 O(N^2)。