知识卡片
次线性查询还要计入输出
当0<α时n^α比n增长慢,但具体查询上界依赖维度、树形态、查询类型及返回结果数量。书中提到平衡kd树的区间查询O(n^(1−1/d));如果需要报告k个结果,至少还有输出k项的成本,且维度d、输入假设不能省略。
这只是本节提名的模型,不把它当所有kd树查询和任意维度下的无条件保证;具体构造和查询实现留第9章。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
kd树,它能够高效地划分n个多维点。如果这种树是平衡树,那么区间查询的查询时间将会是O(n1-1/d)。
参考来源
- 位置:《算法技术手册》第2章《讨论2:次线性的算法的性能,时间复杂度为O(nd),d<1》(spine1468;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1432.html;u033-ch02-010)。
- 结论依据:33全文及原始指数含义实读,输出成本为直接推导。
- 原始内容:kd树,它能够高效地划分n个多维点。如果这种树是平衡树,那么区间查询的查询时间将会是O(n1-1/d)。