mergesort計數比較

Question

我通過Python做了mergesort，它工作正常。我需要計算比較，當這種合併排序正在運行。我聲明全局變量'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