我有一个未知的算法，我需要计算 (Big O) 的时间复杂度。 关于该算法，我唯一知道的是完成给定数量的值需要多长时间。 为了清楚起见，该算法采用一个数字并返回使用该数字时所花费的时间。
如果根据所用时间和给定数字绘制所用时间图，我会根据所用时间和当时给出的数字得出一条近乎直线的曲线。该行非常适合 O(n log n) 的复杂性。问题仍然是即使这条线确实适合，我也无法证明复杂度真的是 n log n。那么我怎样才能证明复杂性呢？
以下是一些值:
time: 0.008 number of elements: 4000
time: 0.100 number of elements: 40000
time: 0.1200 number of elements: 400000
time: 1.4000 number of elements: 4000000
最佳答案
评论是正确的:你无法证明复杂性，你需要更多的点来根据经验对其建模。您当前数据的图表显示了这一点。
如果您获得更多数据，您可以做的一件事是调查它 log-log plot , 绘制时间 t 的日志对元素数 n 的日志。如果您的关系的形式为:t = n^p，这将为您提供一条梯度为 p 的直线，如下面一些模拟数据所示。黑点表示 y=x^2 关系，绿色表示 y=x，红色表示 y=x*log(x) 介于两者之间。
如果您认为这是一个 nlogn 关系，您可以简单地将 t 与 nlogn 作图，您应该得到一条直线。回归分析当然是可能的，但如果您查看当前数据，您实际上会从线性回归中得到非常好的直线拟合(如上图第一个图所示)，我当然不会在此基础上说它是线性的.
关于performance - 未知算法的大O，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22709725/