C*****n
发帖数: 1049 | 1 多次发现换了一个更快的算法后，runtime的时间居然更长。估计是因为1000次左右的
测试也就几毫秒，受测试时cpu的load影响很大。 |
o*********r
发帖数: 203 | 2 For small input sizes (i.e. <= 1000), Programs in better algorithms don't
mean they will take less time time to run. In such cases, O(N^2) may even
run
faster than O(n). You may only see big difference for a very large input
sizes.
From Wiki:
--In mathematics, big O notation describes the limiting behavior of a
function when the argument tends towards a particular value or infinity.-- |
g*****g
发帖数: 34805 | 3 是的，所以实战中如果确定数据不大，你用冒泡还是快排是没有区别的。
【在 o*********r 的大作中提到】
: For small input sizes (i.e. <= 1000), Programs in better algorithms don't
: mean they will take less time time to run. In such cases, O(N^2) may even
: run
: faster than O(n). You may only see big difference for a very large input
: sizes.
: From Wiki:
: --In mathematics, big O notation describes the limiting behavior of a
: function when the argument tends towards a particular value or infinity.--
|
C*****n
发帖数: 1049 | 4 那是，算法的速度还有常数项。
我在leetcode上验证的是同样速度级别的算法，比如O(N)= c1 N 和c2 N, 这里常数c1
明显比c2小得多的时候，c1 N 这个算法用的runtime还更大。
【在 o*********r 的大作中提到】
: For small input sizes (i.e. <= 1000), Programs in better algorithms don't
: mean they will take less time time to run. In such cases, O(N^2) may even
: run
: faster than O(n). You may only see big difference for a very large input
: sizes.
: From Wiki:
: --In mathematics, big O notation describes the limiting behavior of a
: function when the argument tends towards a particular value or infinity.--
|
S********t
发帖数: 3431 | 5 不光是常数项，很多early termination or pruning技巧，runtime也跟test case有关
c1
【在 C*****n 的大作中提到】
: 那是，算法的速度还有常数项。
: 我在leetcode上验证的是同样速度级别的算法，比如O(N)= c1 N 和c2 N, 这里常数c1
: 明显比c2小得多的时候，c1 N 这个算法用的runtime还更大。
|
w**z
发帖数: 8232 | 6 估计Lc 是run 在cloud 上，估计也不是啥好的instance, cpu steal 很正常。
【在 C*****n 的大作中提到】
: 多次发现换了一个更快的算法后，runtime的时间居然更长。估计是因为1000次左右的
: 测试也就几毫秒，受测试时cpu的load影响很大。
|
