c++ O(N*N)时间复杂度的计算

ehxuflar  于 2022-12-05  发布在  其他
关注(0)|答案(1)|浏览(202)

I(NN)的时间复杂度,这是一个复杂度为O(NN)的循环。

for(i = 0; i < N-1; i++){
            for(j = i+1; j < N; j++){
                if((A[j] > B[i])){
                    ctr++; //counting elements satisfying the condition
                }
            }
        }

A和B只是两个向量。我期望减少O(N*N)到O(N)。另外,我怀疑排序A和B是否有帮助!谢谢!

bwntbbo3

bwntbbo31#

如果您要比较NN/2个任意元素,则需要NN/2次运算,即O(n²)。排序是O(Nlog(N)),并且可以分别对两个向量进行排序。对两个向量进行排序仍然是O(Nlog(N)),因为常量因子在Big-O表示法中不起作用。
如果向量已经排序,您可以在第一个不满足条件的元素之后中断循环。

相关问题