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。在后一种情况下，除非您m视为常量而不是变量，否则它是O(n^3 * m^2)的。在 Big-O 表示法中，您不需要只有一个变量来表示输入数据的大小。

Answer 2

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

正确。

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

两者都是正确的。这取决于您m是变量还是常量。

Answer 3

在渐近符号中，可以有多个变量。对于考虑 n 和 m 作为变量的第二种情况，复杂度将为 O（n^3 * m^2）。如果将 m 视为常数，则复杂度为 O（n^3）。