《算法技術手冊》一2.4.3 次線性級算法O(nd)(d<1)的性能

在某些情況下，次線性算法的性能要好于線性算法，但還是不如對數算法高效。第10章将會讨論多元k-d樹，它能夠高效地劃分n個d維的點。如果k-d樹是平衡樹，那麼區間查詢的性能為

，在二維的情況下，最終性能為O(sqrt(n))。