0

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

对于“最接近的点对”问题（不熟悉的请看这个），为什么蛮力算法的最坏情况运行时间是 O(n^2)？

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

O(n^2) 不适合我。

4

4 回答 4

4

实际比较次数为：

精确公式, 或在此处输入图像描述.

但是，在大 O 表示法中，您只关心主导项。在 的值非常大时在此处输入图像描述，在此处输入图像描述项变得不那么重要，项的在此处输入图像描述系数也是如此<code>n^2</code>。所以，我们只说它是<code>O(n^2)</code>.

Big-O 表示法并不意味着为您提供所用时间或步数的确切公式。它只为您提供复杂性/时间的顺序，因此您可以了解它如何针对大输入进行扩展。

于 2017-01-17T19:49:32.770 回答
2

施加蛮力，我们被迫检查所有可能的对。假设有 N 个点，对于每个点，还有 N-1 个其他点需要我们计算距离。所以计算的总可能距离 = N 点 * N-1 个其他点。但在这个过程中，我们重复计算了距离。无论是计算 A 到 B 还是 B 到 A，A 到 B 之间的距离都保持不变。因此 N*(N-1)/2。因此 O(N^2)。

于 2017-01-17T19:50:59.513 回答
1

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

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

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

于 2017-01-17T19:45:02.253 回答
1

在算法的蛮力版本中，您比较所有可能的点对。对于每个n点，您还有(n - 1)其他点要比较，如果我们在进行比较后拿走每一对点(n * (n - 1)) / 2。的悲观复杂性O(n^2)意味着操作的数量受限k * n^2于某个常数k。大 O 表示法不能告诉您操作的确切数量，而是一个函数，当数据 ( n) 的大小增加时，它与它成正比。

于 2017-01-17T19:47:32.393 回答