我的程序输出如下:
[[1000, 1500, 2000, 2500, 3000, 3500, 4000],
[437, 680, 917, 1115, 1476, 1668, 1912]]
它是通过 Numpy 库创建的二维数组。第一行是我传递给函数的 N 的数量，第二行是这个函数的时间测量(以微秒为单位)(例如 N=1000 time=437，N=1500 time=680)。
有什么简单的方法可以判断这个函数的复杂度是多少？我知道我可以画一个图然后只看到这个但我的应用程序只需要给我答案(你的函数是(当然可能)O(n) 或 O(n log n) 或 O(n^2)) .
O(n) 似乎很明显 - 我只需要为所有数组除以 N/t 并检查它是否恒定，但我不知道如何检查另外两个？
最佳答案
可以使用 sklearn 进行各种奇特的曲线拟合和模型评估。但是对于一种简单的方法，测量预期为常数的事物的对数的方差就可以了。也就是说，
- 取比值，例如 T/N、T/(N*log(N)) 或 T/N**2。我们希望它保持不变。
- 取该比率的对数，以消除缩放的影响。
- 使用
np.var计算数据点的方差。方差最小的模型获胜。
例如:
import numpy as np
n = np.array([1000, 1500, 2000, 2500, 3000, 3500, 4000])
t = np.array([437, 680, 917, 1115, 1476, 1668, 1912])
print(np.var(np.log(t/n))) # 0.001545...
print(np.var(np.log(t/(n*np.log(n))))) # 0.001348...
print(np.var(np.log(t/(n**2)))) # 0.18049...
所以它绝对不是二次方的。 N*log(N) 比线性拟合稍微好一些。 (尝试一些其他的东西，似乎 N*sqrt(log(N)) 是最好的。)
关于python - Python 中的时间复杂度 - 大 O 表示法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43814652/