[算法] 实证分析

最近又重温了一下算法课中的实证分析。

• 首先针对不同大小的输入获取运行时长。
• 可以通过标准坐标图或双对数坐标图查看运行时常与输入大小的关系。
• 通过成倍增加输入量，可以更便利地估算T(N)与N之间的幂指数关系。 lg( T(N) ) = b lg( N ) + c 即 T(N) = a N^b, 其中 a = 2^c b = ( lg( T(2N₁) ) - lg( T(N₁)) ) ) / ( lg(2N₁)) - lg( N₁) ) ) = lg( T(2N₁)) ) -lg( T(N₁)) ) a = T(2N₁)) / (2N₁))^b

可以教程上第二行就可以计算出b，这就有点不对头了。时常为零，意味着取对数的结果是-∞。返回数值是以毫秒为单位的，因此一般时长也应该是为毫秒为单位的。估计教程上时常实际精度为三位而显示精度为一位，导致不一致的。 下图是我用Excel根据教程显示数据计算的结果：