kNN-DTW 时间复杂度
kNN-DTW time complexity
我从各种在线资源中发现 DTW 的时间复杂度是二次方的。另一方面，我还发现标准 kNN 具有线性时间复杂度。但是，当它们配对在一起时，kNN-DTW 有二次时间还是立方时间？
本质上，kNN 的时间复杂度是否仅取决于所使用的度量？我还没有找到任何明确的答案。
这里需要小心。假设你的 'training' 集合中有 n 个时间序列（我们称它为这个，即使你没有真正使用 kNN 进行训练）长度为 l。计算一对时间序列之间的 DTW 具有 O(l * m) 的渐近复杂度，其中 m 是最大扭曲 window。由于 m <= l O(l^2) 也成立。 （虽然可能有更有效的实现，但我认为在大多数情况下它们实际上并没有更快，参见 here）。使用 kNN 对时间序列进行分类需要您计算该时间序列与训练集中所有时间序列之间的距离，这意味着 n 比较，相对于 n.
线性
因此您的最终复杂度为 O(l * m * n) 或 O(l^2 * n)。换句话说：复杂度与时间序列长度成二次方，与训练样例数成线性关系。
我从各种在线资源中发现 DTW 的时间复杂度是二次方的。另一方面，我还发现标准 kNN 具有线性时间复杂度。但是，当它们配对在一起时，kNN-DTW 有二次时间还是立方时间？
本质上，kNN 的时间复杂度是否仅取决于所使用的度量？我还没有找到任何明确的答案。
这里需要小心。假设你的 'training' 集合中有 n 个时间序列（我们称它为这个，即使你没有真正使用 kNN 进行训练）长度为 l。计算一对时间序列之间的 DTW 具有 O(l * m) 的渐近复杂度，其中 m 是最大扭曲 window。由于 m <= l O(l^2) 也成立。 （虽然可能有更有效的实现，但我认为在大多数情况下它们实际上并没有更快，参见 here）。使用 kNN 对时间序列进行分类需要您计算该时间序列与训练集中所有时间序列之间的距离，这意味着 n 比较，相对于 n.
因此您的最终复杂度为 O(l * m * n) 或 O(l^2 * n)。换句话说：复杂度与时间序列长度成二次方，与训练样例数成线性关系。