最近的一对蛮力;为什么O（n ^ 2）？

Question

问这个问题我觉得很蠢，但......

对于“最接近的点对”问题（如果不熟悉它，请参见this），为什么蛮力算法O（n ^ 2）的最坏情况运行时间？

如果说n = 4，那么在搜索空间中只有12个可能的点要比较，如果我们也考虑从两个方向比较两个点。如果我们两次不比较两点，那么它将是6。

O（n ^ 2）并不等于我。

Answer 1

实际的比较数是：

，或。

但是，在大O符号中，你只关心占主导地位的术语。在非常大的值时，项变得不那么重要了，项上的系数也变得不那么重要了。所以，我们只是说它是。

Big-O表示法并不意味着为您提供所用时间或步骤数的确切公式。它只给出了复杂度/时间的顺序，以便您了解它如何针对大输入进行缩放。

Answer 2

施加蛮力，我们被迫检查所有可能的对。假设N个点，对于每个点，我们需要计算距离的N-1个其他点。因此计算的总可能距离= N点* N-1个其他点。但在过程中我们将距离加倍。 A到B之间的距离保持是否计算A到B或B到A.因此N *（N-1）/ 2。因此O（N ^ 2）。

Answer 3

在big-O表示法中，您可以将乘法常数分解出来，因此：

O(k*(n^2)) = O(n^2)

我们的想法是，常数（OP示例中的1/2，因为距离比较是反射的）并没有真正告诉我们任何关于复杂性的新内容。输入的平方仍然会变大。

Answer 4

在算法的暴力版本中，您可以比较所有可能的点对。对于每个n点，你有(n - 1)其他点进行比较，如果我们拿走每一对，一旦我们最终得到(n * (n - 1)) / 2比较。 O(n^2)的悲观复杂性意味着操作的数量受到k * n^2的约束，对于某些恒定的k。 Big O表示法不能告诉您操作的确切数量，而是在数据大小（n）增加时与其成比例的函数。