time-complexity - kNN-DTW 时间复杂度

Question

我从各种在线资源中发现 DTW 的时间复杂度是二次的。另一方面，我还发现标准 kNN 具有线性时间复杂度。但是，将它们配对时，kNN-DTW 是二次时间还是三次时间？

本质上，kNN 的时间复杂度是否仅取决于所使用的度量？我还没有找到任何明确的答案。

Answer 1

你需要在这里小心。假设n您的“训练”集中有时间序列（我们称它为，即使您并没有真正使用 kNN 进行训练）长度为l。计算一对时间序列之间的 DTW 具有 O( l* m) 的渐近复杂度，其中m是您的最大扭曲窗口。因为m<=l也 O( l^2) 成立。（尽管可能有更有效的实现，但我认为在大多数情况下它们实际上并不快，请参见此处）。使用 kNN 对时间序列进行分类需要计算该时间序列与训练集中所有时间序列之间的距离，这意味着n比较，相对于 是线性的n。

因此，您的最终复杂性将在 O( l* m* n) 或 O( l^2 * n) 中。换句话说：复杂度与时间序列长度成二次方，与训练样例数量成线性关系。