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 的大作中提到】
: 你还能想到这么多, 我只能想到如果用O(N)会用很多空间的话，可以用O(N2).
|
m*****n
发帖数: 2152 | 4 指的是额外空间，O(n)要用到额外空间，O(n^2)可能不用额外空间，本身的O(n)空间和
算法没关系吧。
【在 c*******y 的大作中提到】
: 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. |
