logging - 关于算法复杂度测量

Question

嘿伙计们，我是新来的，所以我会尽量保持清楚。

在我目前的练习中，我将展示几种排序算法之间的时间差异。为了获得更精确的结果，我采用了几个不同大小的数组（已排序、未排序）并得到了我的结果。我理解 o、big O 等的含义……所以我的问题是关于 theta 在归并排序中的含义。更清楚地说，我知道这个特定算法的复杂性是 n*log(n)，我不明白的是，当我在大小为 2000 的数组中获得例如 15000 毫秒的结果时会发生什么 - 如果我把它在函数 n*log(n) 中，我不应该得到与系统提供的相同的数字吗？或者我是不是乳清了？

我希望我的问题可以理解，谢谢。

Answer 1

Big O 表示算法性能接近极限时的趋势，而不是表示任何特定 N 值的结果。例如，如果算法的性能可以表示为 f(x) = 2x + x^ 2，那么它有 x^2 的大 O。

此外，Big O 是独立于硬件的。

如果您想查看您的时间与大 O 之间的关系，请多次运行该算法并增加 n 值并绘制结果图表。您会看到时间遵循类似于 Big O 所描述的图表。