首页分别给出Nearest Neighbor、Nearest Insertion、Farthest Insertion、2-Opt、 Christoﬁﬁdes和LKH算法的时间复杂度和空间复杂度

分别给出Nearest Neighbor、Nearest Insertion、Farthest Insertion、2-Opt、 Christoﬁﬁdes和LKH算法的时间复杂度和空间复杂度

时间: 2023-07-10 21:31:01 浏览: 163

k-Nearest Neighbor Classification

this paper, the problem of classifying an unseen pattern on the basis of its nearest neighbors in a recorded data set is addressed from the point of view of Dempster-Shafer theory. Each neighbor of a sample to be classified is considered as an item of evidence that supports certain hypotheses regarding the class membership of that pattern. The degree of support is defined as a function of the distance between the two vectors. The evidence of the k nearest neighbors is then pooled by means of Dempster's rule of combination. This approach provides a global treatment of such issues as ambiguity and distance rejection, and imperfect knowledge regarding the class membership of training patterns. The effectiveness of this classification scheme as compared to the voting and distance-weighted k-NN procedures is demonstrated using several sets of simulated and real-world data.

Nearest Neighbor (NN)算法：时间复杂度：$O(n^2)$ 空间复杂度：$O(n)$ Nearest Insertion (NI)算法：时间复杂度：$O(n^3)$ 空间复杂度：$O(n^2)$ Farthest Insertion (FI)算法：时间复杂度：$O(n^3)$ 空间复杂度：$O(n^2)$ 2-Opt算法：时间复杂度：$O(n^3)$ 空间复杂度：$O(n^2)$ Christoﬁﬁdes算法：时间复杂度：$O(n^3)$ 空间复杂度：$O(n^2)$ LKH算法：时间复杂度：$O(n^2)$ 空间复杂度：$O(n^2)$ 这里的n表示城市的数量。需要注意的是，这些算法的时间复杂度和空间复杂度都是在最坏情况下的复杂度，实际情况下可能会更好。

阅读全文