python - 合并排序中的比较计数

Question

我用Python进行了合并排序，它工作正常。并且我需要在这个合并排序运行时计算比较。我声明全局变量“merge_compare_count”，因为这是递归函数。我对列表 A 的元素使用随机数。

但问题是每当我运行此代码时，我总是得到相同的 merge_compare_count。我不知道为什么......

例如，当 A 获得 5000 个随机不同的元素，但 merge_compare_count 始终返回与 123616 相同的元素时。

任何帮助将不胜感激!!

Answer 1

这不是问题。按照其编写方式，您的代码仅具有确定的步骤数量，仅取决于大小，而不取决于值。您甚至可以像这样计算它们:

>>> def f(n):
        return 0 if n < 2 else f(n/2) + f(n-n/2) + 2*n

>>> f(5000)
123616