原书出处
算法技术手册
递归来迭代维度的每个坐标。它从点集中选择
中位元素,然后将在这个元素“下方”的元素插入左子树,“上方”的元素插入右子树。这段代码适用于任何维度。 例9-4:递归构建kd树 选择操作在第4章的“快速排序”一节中已经描述过了。能够在平均情况下在O(n)时间内选择第k小的元素,但是,在最坏情况下会退化到O(n2)的性能。为了避免这种情况,我们使用
BFPRT选择算法,在第4章中我们讨论过
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1627.html
EPUB SHA-256:06582ecdf071724c9e218bc2698d2fff4e82a992d672b287e4c2e6092c924bcf