level 3
我用move和二分查找实现一个单调递增队列,目的是快速读取最小值。
结果比人家用堆慢很多,是不是move太慢了?
2016年05月29日 06点05分
1
level 3
var
a:array[1..1000000] of longint;
i:longint;
begin
for i:=1 to 10000000 do move(a[1],a[100000],40000)
end.
用我家电脑测出来66秒,这倒不是重点,重点是我通过试验发现move速度随第三个参数(内存块长度)线性增长,以前一直以为是常数
2016年05月29日 06点05分
2
level 3
楼主就好比社区的明灯,楼主就好比社区的方向,楼主就好比社区的栋梁。
2016年06月09日 03点06分
6
level 6
move当然不是O(1)啦,
要更改O(n)的内存,时间也是O(n),优先队列用数组和链表实现都免不了O(n)时间的操作,用不用move在时间复杂度上没有本质区别,用堆实现才能做到单次操作O(log n)
2016年06月15日 14点06分
7