最坏的运行时间Big O.

Question

你能解释一下我如何能得到这个算法的最坏情况Big O. 我正在阅读我的教科书,我遇到了类似这样的算法,但仍然不理解它背后的逻辑.

int t=0;
for(int x=0;x<num.length;x++){
    for(int y=0;y<num.length;y++){
        for(int p=0;p<num.length;p++){
            for(int w=0;w<num.length;w++){
                if(num[p][w]>num[x][y])
                {
                    t=num[x][y];
                    num[x][y]=num[p][w];
                    num[p][w]=t;
                }
            }
        }
    }
} 

Answer 1

逻辑非常简单.让我们从最内循环开始:

这个循环运行num.length时间.最大的情况是大O符号的运行时复杂性O(n)假设n = num.length.

for(int w=0;w<num.length;w++){
    ...
}

现在当你在它的长度周围放置另一个for循环时p,它将运行上面的for循环p时间.就是这样O(pn).在你的情况下,p = num.length = n它应该是O(n*n) = O(n^2).

您的示例中有4个嵌套循环,所以答案是O(n^4).

为什么我忽略了最内循环的内容？因为完成了一定数量的操作,所以请记住这个数字c.big-O表示法使用的渐近分析如下:O(c) is equivalent to O(1).这来自big-O的定义.