m*****n 发帖数: 2152 | 1 When should you use an O(N^2) algorithm over an O(N) algorithm?
这道题很奇怪,和正常想法反着来的。
想到的是以下几点:
1. when time complexity is not critical,and space complexity is more
important while O(n^2) algorithm has better space complexity.
2. when time complexity is not critical,bug free coding for O(n^2) is much
easier and faster than O(n).
3. when n is always finite and can never be very large.
还有什么可以说的? |
Q**F 发帖数: 995 | 2 你还能想到这么多, 我只能想到如果用O(N)会用很多空间的话,可以用O(N2). |
c*******y 发帖数: 98 | 3 O(N)最多用O(N)空间吧,否则初始化已经超过O(N)了。
【在 Q**F 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你还能想到这么多, 我只能想到如果用O(N)会用很多空间的话,可以用O(N2).
|
m*****n 发帖数: 2152 | 4 指的是额外空间,O(n)要用到额外空间,O(n^2)可能不用额外空间,本身的O(n)空间和
算法没关系吧。
【在 c*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : O(N)最多用O(N)空间吧,否则初始化已经超过O(N)了。
|
A***g 发帖数: 1816 | 5 我想到一个,有可能,你n^2的算法可以很容易使用平行计算,而你恰好有现成的硬件
环境,这样可能实际的使用速度反而快
另外一个情况,就是n不够大,而每个算法的实际时间是K*n^2, G*n,K和G是常数。如
果n不够大,而G又远比K大,那么n^2的速度反而快了 |
l***i 发帖数: 1309 | 6 O(n) or O(n^2) only tells you asymptotic behavior, O(n) could be 100000 * n
while O(n^2) could be 1 * n^2, depends on your n, O(n^2) might be faster.
plus a number of reasons already mentioned earlier. |