知识卡片

普通读书笔记卡 · 1708.b.3.i · 生成模型:未记录

次线性查询还要计入输出

理解等级:中级

当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)。