最近的一对点蛮力；为什么是 O(n^2)？
Closest pair of points brute-force; Why O(n^2)?
我觉得问这个问题很愚蠢，但是...
对于"closest pair of points"问题（不熟悉的请看this），为什么暴力算法的最坏情况运行时间为O(n^2) ？
如果说 n = 4，那么在搜索中只有 12 个可能的点可以比较 space，如果我们还考虑从任一方向比较两个点。如果我们不比较两个点两次，那么它将是 6.
O(n^2) 加起来不合我意。
在 big-O 表示法中，您可以分解出相乘的常数，因此：
O(k*(n^2)) = O(n^2)
想法是常数（在 OP 示例中为 1/2，因为距离比较是反射性的）并没有真正告诉我们任何关于复杂性的新信息。它仍然随着输入的平方而变大。
在算法的 brute-force 版本中，您比较所有可能的点对。对于 n 个点中的每个点，您还有 (n - 1) 个其他点要比较，如果我们对每一对进行一次比较，我们最终会进行 (n * (n - 1)) / 2 个比较。 O(n^2) 的悲观复杂性意味着对于某个常数 k，操作数受 k * n^2 约束。大 O 表示法不能告诉您确切的操作数，而是一个函数，它与数据大小 (n) 增加时成正比。
实际比较次数为：
, or 。
但是，在 big-O 表示法中，您只关心主导项。在 , the term becomes less important, as does the coefficient on the term. So, we just say it's 的非常大的值。
Big-O 表示法并不意味着为您提供所用时间或步数的确切公式。它只为您提供 complexity/time 的顺序，因此您可以了解它如何针对大输入进行扩展。
使用蛮力，我们被迫检查所有可能的 pairs.Assuming N 个点，对于每个点，我们需要计算距离的其他 N-1 个点。所以计算出的总可能距离 = N 点 * N-1 其他点。但在这个过程中，我们重复计算了距离。无论计算 A 到 B 还是 B 到 A，A 到 B 之间的距离保持不变。因此 N*(N-1)/2。因此 O(N^2).
我觉得问这个问题很愚蠢，但是...
对于"closest pair of points"问题（不熟悉的请看this），为什么暴力算法的最坏情况运行时间为O(n^2) ？
如果说 n = 4，那么在搜索中只有 12 个可能的点可以比较 space，如果我们还考虑从任一方向比较两个点。如果我们不比较两个点两次，那么它将是 6.
O(n^2) 加起来不合我意。
在 big-O 表示法中，您可以分解出相乘的常数，因此：
O(k*(n^2)) = O(n^2)
想法是常数（在 OP 示例中为 1/2，因为距离比较是反射性的）并没有真正告诉我们任何关于复杂性的新信息。它仍然随着输入的平方而变大。
在算法的 brute-force 版本中，您比较所有可能的点对。对于 n 个点中的每个点，您还有 (n - 1) 个其他点要比较，如果我们对每一对进行一次比较，我们最终会进行 (n * (n - 1)) / 2 个比较。 O(n^2) 的悲观复杂性意味着对于某个常数 k，操作数受 k * n^2 约束。大 O 表示法不能告诉您确切的操作数，而是一个函数，它与数据大小 (n) 增加时成正比。
实际比较次数为：
但是，在 big-O 表示法中，您只关心主导项。在
Big-O 表示法并不意味着为您提供所用时间或步数的确切公式。它只为您提供 complexity/time 的顺序，因此您可以了解它如何针对大输入进行扩展。
使用蛮力，我们被迫检查所有可能的 pairs.Assuming N 个点，对于每个点，我们需要计算距离的其他 N-1 个点。所以计算出的总可能距离 = N 点 * N-1 其他点。但在这个过程中，我们重复计算了距离。无论计算 A 到 B 还是 B 到 A，A 到 B 之间的距离保持不变。因此 N*(N-1)/2。因此 O(N^2).