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

我正在学习如何在学校做时间复杂度，教授上传了一些例子。在下面的第一个例子中，答案应该是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）。有人能给我关于上述问题的提示吗说到这一点，我感到不知所措，到目前为止，我一直在解决其他问题。

最佳答案

计算BigO时的一个基本假设是去掉非支配项。
使用第一个例子，
外循环的顺序为o（n^2）
内环的顺序为O（n^3）
内部循环独立运行“n”次，但由于它是嵌套的，因此将运行“n*（n^2）”。
'
因此，BigO的形式是O（（n^2）+（n^3）），这就足够O（n^3）。
你可以试着用同样的方法解决第二个问题。
如果您还有些困惑，请看以下视频：
Big O Notation

关于java - 大O-不了解这些算法的时间复杂度吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42381102/