我应该使用哪种统计方法来比较两种算法的机器运行时间?

计算科学 统计数据 可视化 数据分析
2021-12-06 03:12:17

我通过解决问题的不同实例来比较两种算法的运行时间。我的数据样本:

 problem_id  |  algo_original_time  |  algo_improved_time
---------------------------------------------------------
 prob_01     |  0.56                |  0.036
 prob_02     |  0.26                |  0.005
 prob_03     |  0.75                |  0.055
 ....

请注意,所有问题实例都是不同的,它们没有任何相关性。

我已经使用交叉验证图来表示数据。有没有更好的方法/统计方法来比较这两种算法的运行时间。

1个回答

这是配对 t-test的典型用例。这个想法是只考虑运行时差异 Δt对于每个问题并检验原假设E(Δt)=0. 有关分步说明,请参阅例如(文章指的是分段评估,但在抽象层面上,问题与您的问题相同):

Mao, Kanungo:“经验性能评估方法及其在页面分割算法中的应用”。IEEE Transactions on Pattern Analysis and Machine Intelligence 23 (3), pp. 242-256 (2001)