time-complexity - kNN-DTW 时间复杂度
问题描述
我从各种在线资源中发现 DTW 的时间复杂度是二次的。另一方面,我还发现标准 kNN 具有线性时间复杂度。但是,将它们配对时,kNN-DTW 是二次时间还是三次时间?
本质上,kNN 的时间复杂度是否仅取决于所使用的度量?我还没有找到任何明确的答案。
解决方案
你需要在这里小心。假设n
您的“训练”集中有时间序列(我们称它为,即使您并没有真正使用 kNN 进行训练)长度为l
。计算一对时间序列之间的 DTW 具有 O( l
* m
) 的渐近复杂度,其中m
是您的最大扭曲窗口。因为m
<=l
也 O( l
^2) 成立。(尽管可能有更有效的实现,但我认为在大多数情况下它们实际上并不快,请参见此处)。使用 kNN 对时间序列进行分类需要计算该时间序列与训练集中所有时间序列之间的距离,这意味着n
比较,相对于 是线性的n
。
因此,您的最终复杂性将在 O( l
* m
* n
) 或 O( l
^2 * n
) 中。换句话说:复杂度与时间序列长度成二次方,与训练样例数量成线性关系。
推荐阅读
- neo4j - 获取满足 Neo4J 条件的断开连接的集群数量
- typescript - TypeScript:获取真实类中抽象方法实现的类型
- php - 将 DOCX / Word 生成的 XML 转换为 JSON
- python - 传递变量参数:python
- python-3.x - 如何初始化python看门狗模式匹配事件处理程序
- javascript - 加载项中的 Outlook 对话框无需停用浏览器上的弹出块即可使用
- ios - 如何设置视图的颜色以匹配半透明导航栏的颜色?
- visual-studio - 通过 Wix 安装程序安装我的 VSTO 加载项后,当我打开 Outlook 时,它要求再次安装
- arrays - 保存和加载结构数组的最佳做法是什么?
- c# - Topshelf 服务找不到 dll