algorithm - 想知道我的脚本的大 O 符号值吗？

Question

自从我估计某事的大 O 符号以来已经有一段时间了，我似乎无法掌握这个。基本上，我的脚本遍历美国的经纬度点列表，如果这些点是半径为 100 英里的圆心，则找到一个覆盖该国的集合。所以像这样：

• 开始循环遍历列表，索引 i = 0。
• 找出列表中第 i 个点与列表中所有跟随它的点之间的距离。
• 删除 100 英里范围内的所有点
• 重新索引数组
• 将索引增加一
• 如果 i = 列表长度，结束，否则，循环

Answer 1

你的算法是O(N^2)，在哪里n。如果我正确理解您的描述，它会是这样的：

for point A in array:
  for point B in array:
      d = dist(A,B)
      //optionally remove from list

在最坏的情况下，每对点相距超过 100 英里，因此您最终会检查每对点之间的距离，因此O(N^2).

请注意，您最多进行n + (n-1) + (n-2) + ... + 2 + 1 = (n(n+1))/2距离计算，仍然是O(N^2).

Answer 2

您的算法的运行时间是O(n^2)，因为在最坏的情况下，您遍历数组并根据数组中的所有以下点检查每个点，从而n(n-1)/2进行比较，即O(n^2)

我必须告诉你，我认为这个算法不能为你的问题提供正确的解决方案。

Answer 3

假设n是您作为输入的点数。

开始循环遍历列表，索引 i = 0。

...

如果 i = 列表长度，结束，否则，循环

这就是n迭代。

找出列表中第 i 个点与列表中所有跟随它的点之间的距离。

这是n每次迭代的操作。如果只是这两个，它最终会是n^2/2（每个点与其他点，除了顺序无关紧要，所以你做了一半的比较）。

删除 100 英里范围内的所有点

重新索引数组

听起来，您将 100 英里内的那些元素归零，然后移动数组。这两者都是O(n)操作，最终是O(n^2)因为您O(n)重复了操作n。

所以你最终拥有O(n^2).