这段代码的时间复杂度是多少？

Question

我有点困惑，我知道在外循环中如果 i < n 并且在内部循环中如果 j < i 那么复杂度将是 O(n^2) 但是如果我们从 n 和 i 增加限制分别对 n^2 和 i^2 复杂度是像 O(n^4) 一样加倍还是变成立方 O(n^3)？

   for(long i = 1; i < n*n; i++)
                {
                    for(long j = 1; j < i * i; j++)
                    {
                      //some code  
                    }
                }

Answer 1

假设//some code需要O(1)次操作，时间复杂度为O(n^6)。由于内部循环需要 i^2 - 1 次迭代，您可以使用平方和公式（或等效地使用 Wolfram alpha）来获得