文件名称：extra-lecture-kdtrees:kdtrees 的讲义
文件大小：3KB
文件格式：ZIP
更新时间：2024-08-03 06:12:43
CS558：kd 树 问题陈述 正交范围 $I \subset \mathbb{R}^d$ 是（可能是*的）区间的乘积。 令 $S$ 是欧几里得空间中的一组 $n$ 点。 然后正交范围搜索问题是找到$S$中包含在$I$中的所有点的集合。 我们如何处理这里的结果有一些变化。 我们可能会计算所有的点，计算一些总量（即 map/reduce 类型的操作），甚至只是报告恰好位于范围内的所有点。 我们将专注于后一个版本 有一个明显的 O(n) 算法可以解决这个问题，如果我们不对这些点做任何预处理，这是最优的。 事实上，因为任何搜索都可能返回一个区间内的所有点，看起来 O(n) 实际上是最坏情况性能的严格界限。 然而，如果我们更小心一点，我们可以将复杂性分离为数据结构中点数以及返回点数（我们称之为 k）的函数。 在这个更详细的分析下，naive range search的复杂度是O(n + k)。
【文件预览】：
extra-lecture-kdtrees-master
----README.md(7KB)