为什么在我的电脑里比较heapify和普通的add操作，heappify的效率更低呢？
来源：8-5 Heapify 和 Replace
慕田峪2263497
2020-03-28
第一次：
Test MaxHeap completed
Without heapify: 0.7828384s
Test MaxHeap completed
With heapify: 0.8031989s
第二次：
Test MaxHeap completed
Without heapify: 0.7725524s
Test MaxHeap completed
With heapify: 0.8053163s
把老师的代码在本地替换后依然这样（第三次和第四次替换的老师的代码运行的结果）
第三次：
Test MaxHeap completed
Without heapify: 0.7085264s
Test MaxHeap completed
With heapify: 0.7448924s
第四次：
Test MaxHeap completed
Without heapify: 0.7129637s
Test MaxHeap completed
With heapify: 0.7352726s
1回答
-
liuyubobobo
2020-03-29
我在我的环境下，用 100 万级别的数据测试，没有这个问题。如果使用 1000 万级别的数据测试，结果更明显。
建议你使用更大的数据量试试看？
不过 logn 级别的差距的算法，本身差距就是非常非常小的。我做算法竞赛这么多年，O(n) 级别的算法近乎和 O(nlogn) 级别的算法是等同的。也就是一个问题，如果存在 O(n) 级别的算法，但是你的实现是 O(nlogn) 级别的算法的话，OJ 近乎不可能辨别出来。
继续加油！：）
022020-03-31
相似问题