c - for 循环中 n * n * n 次迭代的时间复杂度是多少？

Question

这些循环的时间复杂度是多少？如果我错了，请纠正我。

这个循环是 O(n^3) 因为它有 (n^3)/2 + 1 次迭代。

for (int i = 0; i < n * n * n; i+=2)
{
     //body
}

和

这个循环是 O(n^3 * m^2) 因为它有 (n^3 + 1) * (m^2 + 1) 次迭代。或者这只是 O(n^3)，因为内部循环不是变量 n？

for (int i = 0; i < n * n * n; i+=2)
{
     for (int j = 0; j < m * m; j++)
     {
     //Body
     }
}

Answer 1

在第一种情况下，时间复杂度是O(n^3)。它捕获最重要的项，因此您可以忽略 1/2 的比例因子和常量 +1。在后一种情况下，它是 O(n^3 * m^2) 除非您将 m 视为常量而不是变量。在 Big-O 表示法中，您不必只用一个变量来表示输入数据的大小。