Big O - 不了解这些算法的时间复杂度？

Question

我在学校学习如何做时间复杂度，教授上传了一些例子。对于下面的第一个例子，答案应该是 O(n^3) 但我不明白如何。

public static int fragment1 (int n)
{
    int sum = 0;
    for (int i = 1; i <= n*n; i++) 
       for (int j = 0; j*j < i; j++) sum++;
    return sum;
} // end fragment1

当我尝试这个问题时，我查看了第一个 for 循环，发现它运行了 n^2 次，然后内部 for 循环也是 n^2。加起来我得到 O(n^4)。

public static int fragment5 (int n) 
{
    int sum = 0;
    for(int i=0; i < n*n*n; i++)
    {
        if(i%(n*n) == 0) {
            for(int j=i*i; j > 0; j--)
                sum++;
        } // if
        else
        {
            for(int k=0; k < i: k++)
                sum++;
        } // else
    } // outer loop
}

对于上面的问题，答案应该是O(n^7)。当我尝试它时，我得到：第一个 for 循环运行 n^3 次，内部 for 循环 n^3*n^3 = n^6，以及 else 语句中的 for 循环我得到 n，我的最终答案是 O(n ^10).有人可以给我关于上述问题的提示吗？说到这个，我觉得一头雾水，到目前为止，我一直在解决其他问题。

Answer 1

计算 BigO 时的基本假设之一是删除非主导项。

使用第一个例子，

外环的阶数为 O(n^2)
内循环的阶数为 O(n^3)
- 内部循环独立运行s 进行 'n' 次但是因为它是嵌套的，它将运行进行 'n * (n^2) '

因此，BigO 的形式为 O((n^2) + (n^3))，这足以满足 O(n^3)。

您可以尝试使用相同的技巧来解决第二个问题。
如果你还有一些困惑，请看下面的视频： Big O Notation

Big O - 不了解这些算法的时间复杂度？

Big O - Don't understand time complexity for these algorithms?

java

algorithm

time

complexity-theory