我有一个归并排序的实现。我不太确定我的实现质量，所以我用 N 到 6000 的列表运行它，并绘制了每次排序所花费的时间。我知道合并排序应该是 O(n log n)，但我的图表看起来比对数更线性(可能略微多项式)。我在解释这张图时遗漏了什么吗？此外，我不确定如何看待随着 N 向 6000 增长而增加的价差。这看起来正确吗？
这是我的一些数据值的摘录。请注意其中一些是如何完全相同的。这是意料之中的事吗？
N time (s)
2000 0.023001909
2001 0.023000956
2002 0.023000956
2003 0.028002024
2004 0.023002148
2005 0.023001194
2006 0.024002075
2007 0.023000956
2008 0.023000956
2009 0.023001194
2010 0.023000956
2011 0.023001909
2012 0.024000883
2013 0.023000956
2014 0.022001028
2015 0.024001122
2016 0.023001909
2017 0.024001122
2018 0.024000883
2019 0.023001909
2020 0.023000956
2021 0.024000883
2022 0.023002148
2023 0.024000883
2024 0.024000883
2025 0.024002075
2026 0.023000956
2027 0.024002075
2028 0.023001194
2029 0.024001122
2030 0.023002148
2031 0.024000883
2032 0.023000956
2033 0.024001837
2034 0.023000956
2035 0.024002075
2036 0.028002024
2037 0.024000883
2038 0.024001122
2039 0.024002075
2040 0.024001122
2041 0.023000956
最佳答案
您的图表与平均 O(n log n) 行为一致 - 事实上，它似乎符合接近 1.53e-6 * N * log(N) 的曲线
但可以肯定的是，在一系列更大的列表上运行您的实现。 O(n log n) 只是关于当 n 趋于无穷大时算法如何表现的陈述。您的曲线可能看起来与小输入的线性和多项式曲线无法区分，但随着列表变得越来越大，O(n log n) 算法将与任何 O(n^2) 算法明显区分开来。
关于algorithm - 合并排序实现的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24728007/