Department of Computer Science, University of Joensuu, FIN-80101 Joensuu, Finland.
IEEE Trans Image Process. 2000;9(5):773-7. doi: 10.1109/83.841516.
Straightforward implementation of the exact pairwise nearest neighbor (PNN) algorithm takes O(N3) time, where N is the number of training vectors. This is rather slow in practical situations. Fortunately, much faster implementation can be obtained with rather simple modifications to the basic algorithm. In this paper, we propose a fast O(tauN2) time implementation of the exact PNN, where tau is shown to be significantly smaller than N, We give all necessary data structures and implementation details, and give the time complexity of the algorithm both in the best case and in the worst case. The proposed implementation achieves the results of the exact PNN with the same O(N) memory requirement.
直接实现精确的最近邻（PNN）算法需要 O(N3) 的时间，其中 N 是训练向量的数量。在实际情况下，这是相当慢的。幸运的是，通过对基本算法进行相当简单的修改，可以获得更快的实现。在本文中，我们提出了一种快速的精确 PNN 的 O(tauN2) 时间实现，其中 tau 被证明显著小于 N。我们给出了所有必要的数据结构和实现细节，并给出了算法在最好情况和最坏情况的时间复杂度。所提出的实现以相同的 O(N) 内存需求达到了精确 PNN 的结果。
