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是否有帮助!谢谢!
1条答案
按热度按时间bwntbbo31#
如果您要比较NN/2个任意元素,则需要NN/2次运算,即O(n²)。排序是O(Nlog(N)),并且可以分别对两个向量进行排序。对两个向量进行排序仍然是O(Nlog(N)),因为常量因子在Big-O表示法中不起作用。
如果向量已经排序,您可以在第一个不满足条件的元素之后中断循环。