如果我的问题被严重误导或范围松散,我深表歉意。数学不是我最强的科目。对于上下文,我试图弄清楚计算离散曲线下面积的计算复杂性。在我感兴趣的特定用例中,y 轴是队列的长度,x 轴是时间。曲线将始终具有以下边界:它从零开始,由多个大于零的带时间戳的样本组成,最终收缩到零。我的初步研究已经产生了解决这个问题的两种可能的数学方法。第一个是域 [a, b] 上的 Reimann 和,其中 a 最初为零,b 最终变为零(不确定我的理解是否完全正确)。我认为这个公式的数学表示在这里找到:
https://en.wikipedia.org/wiki/Riemann_sum#Connection_with_integration .
第二种是离散卷积。但是,我无法区分域 [a, b] 上的离散卷积和 Reimann 和之间的区别和适用性,其中 a 最初为零,b 最终变为零。
我的问题是:
- 两者有区别吗?
- 哪种方法最适用/最有效地解决了我想弄清楚的问题?
- 询问这两种数学方法的计算复杂度是否合适?如果是这样,在这个特定的应用程序中每一个的复杂性是什么?
编辑: 对于添加的上下文,将有一个函数计算平均队列长度,方法是将两条单独曲线下的面积之和除以跨越这两条曲线的总时间间隔。具体应用见本文第 168 页:https://www.cse.wustl.edu/~jain/cv/raj_jain_paper4_decbit.pdf
最佳答案
Is there are difference between the two?
A discrete convolution需要两个函数。如果第一个对应离散曲线,那么第二个是什么?
Which approach is most applicable/efficient for what I am trying to figure out?
A Riemann sum是积分的近似值。它通常用于近似连续曲线下的面积。您当然可以在离散曲线上使用它,但它不再是近似值,我不确定您是否可以将其称为“黎曼”和。
Is it even appropriate ask the computation complexity of either mathematical approach? If so, what are the complexities of each in this particular application?
在任何情况下,计算离散曲线下面积的复杂性与样本数量成线性关系,并且很容易找到原因:您需要对每个样本做一次或两次。
您可能想要的看起来像带有 trapezoidal rule 的黎曼和.选择前两个样本,计算它们的平均值,然后将其乘以两个样本之间的距离。对每个相邻的对重复并求和。
关于algorithm - 计算离散曲线下面积的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53142652/