有没有人能给我一个现实的例子,其中一个 O(N*N)
算法比一个 O(N)
算法对于一些 N>10
更快。
编辑:我看到这个问题因为太泛化而被搁置了。但我的问题确实是泛化的。没有其他的方式可以用不同的方式提出这个问题。
for (int i=0;i<N;i++){
// do some expensive preconditioning of your data
// to enable using O(N) algorithm
}
for (int i=0;i<N;i++){
// run the actual O(N) algorithm
}
O(N*N):
for (int i=0;i<N;i++){
for (int j=0;j<N;j++){
// run the O(N*N) algorithm
}
}
O(N) = N + 10000
O(N*N) = N^2 + 0.5*N + 10
输入一个整数n。
第一个例子:一对利用O符号是一个上界的短程序,因此一个O(1)程序也是O(n)和O(n^2)等等...
程序1:
def prog1(n)
1.upto(n) do |i|
end
end
程序2:
def prog2(n)
return
end
程序1是O(n),程序2是O(n*n),以及O(n)、O(1)和O(n^n^n^n^n)。
然而,程序2比程序1更快。
第二个例子:一对利用O符号依赖于n的行为的程序。
程序1:与之前相同
程序2:
def prog2(n)
if n < 10^100
return
else
1.upto(n) do |i|
1.upto(n) do |j|
end
end
end
end
程序1的时间复杂度为O(n),而程序2的时间复杂度为O(n*n)。
然而,当n >= 10^100时,程序2比程序1更快。
O(n^2)
和O(N)
的问题,而是当数据的大小较小时,冒泡排序比快速排序更快,因为快速排序的开销超过了冒泡排序的速度。 - NathanOliver4,8,6,2,999999
的计数排序。您需要扫描一个百万条目的数组才能完成这种类型的排序,但您可以在大约 5*5 次迭代中执行任何“标准”排序。 - barak manos