以下算法的复杂性与最近邻居类似,是什么？

Question

以下算法的时间复杂度是多少？

输入:点P的集合及其欧几里德坐标

1. 计算点的浏览(使用最近邻算法,如TSP问题)

2. 对于每个点,获取最近的邻居信息(相对于原始数据集中的所有点)

复杂度是O(n)还是O(n²)？我们如何轻松地将复杂性和效率可视化？

Answer 1

1. 1. 对于每个点,您必须找到最近的邻居.(你得到第一个n)

   2. 计算两点之间的距离可以得到一个因素1,因为它可以运行O(1).

   3. 因此,计算一个点与所有其他点之间的距离可以得到一个因素O(n).

   你总得到O(n²).当然,在步骤3中,您不必计算到访问点的距离,但这只会保留一个常数因子.

2. 点的最近邻信息A是最近的点A.所以你必须计算n点到所有其他点的距离,所以你也到了这里O(n²)

将这一点加在一起会导致O(n² + n²) = O(2n²) = O(n²).