第31页 | 算法技术手册 | 阅读 ‧ 电子书库

讨论2：次线性的算法的性能，时间复杂度为O(nd)，d＜1

在某些情况下，这种算法的性能好于线性算法，但还是不如对数算法高效。在第9章，我们将会讨论多维kd树，它能够高效地划分n个多维点。如果这种树是平衡树，那么区间查询的查询时间将会是O(n1-1/d)。