1

对于一个项目，我想比较不同中值查找算法的运行时间。我从“Medians of Medians”开始，基本上使用了Geeks for Geeks找到的代码。

我通过与计算中位数的标准 python 方法进行比较来测试它。

if __name__ == '__main__':
    arr = random.sample(range(1, 10000000000), 10000001) 
    arr1=arr[:] # i copied the list to make sure they both have the same starting position 
  
    t1=time.time()
    print("std median", statistics.median(arr))
    t2 = time.time()
    print("time std median:",t2-t1)
    t12 = time.time()
    n = len(arr1)
    k = n // 2 + 1 #median for odd number of elements
    print("Med of Med:", kthSmallest(arr1, 0, n - 1, k))
    t21 = time.time()
    print("time med of med:", t21-t12)

由于未知的原因，我的运行时间太高而且是错误的。在大约 10 个 Mio 元素的数组中查找中位数需要以下时间：

Standard Python method:                  13.28 seconds
My implementation of median of medians:  28.91 seconds

我在 Geek for Geeks 上找到的实现有问题吗？应该反过来。标准 Python 方法的运行时为O(n log n)，Median of Medians 运行在 中O(n)，所以它应该更快！

有谁知道我做错了什么并且可以给我一个提示如何解决它？

4

0 回答 0