如何在收敛图中报告非单调运行时间

计算科学 收敛 可视化 绘图 出版物
2021-12-09 11:23:33

假设我有一个可以通过参数调整的算法h>0并预计收敛为h0.

我想研究这个算法的计算复杂度,即所需的运行时间如何随着精度的增加而增加。为此,我针对不同的值运行算法h(说,h1>h2>>hn>>hN) 并在图中总结这些运行的准确性(与不同的、已建立的方法相比,具有较高的准确性)和运行时间。

该图在水平轴上显示运行时间,在垂直轴上显示精度。但是,有时,随着我的增加,运行时间是非单调的n. 我是否应该重新排序运行,以便绘制一个精度是工作函数的图?

例如,如果我只是连接运行,这些图可能看起来像这样n跑步n+1

在此处输入图像描述

注意运行n=2比跑步花费更多的时间n=3但最终也更加准确。

重新排序的图如下所示。请注意,数据点没有改变,它们只是以不同的顺序连接。

在此处输入图像描述

另一个例子是运行n=2需要更长的时间,但仍然不如n=3. 未洗牌和洗牌的情节将如下所示: 在此处输入图像描述

1个回答

听起来您实际上在这里有三个信息——h、错误和运行时。如果与 h 没有对应关系,则绘制精度与运行时间的关系就没有那么有用了(因此算法的用户不知道如何选择 h 来获得所需的精度/运行时间)。

我会用字形的颜色做散点图来表示h。这样,即使只有字形,您的第一个示例也会清楚地表明这里发生了一些奇怪的事情。重新排序运行隐藏了可能发生某种奇怪的取消/意外行为的事实,因此不期望单调(收敛,运行时间增加)。