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

我已经有一段时间没在某个东西上估计出大的O符号了，我好像没法处理这个基本上，我的脚本运行在一个点的列表中，在美国与纬度/经度，并找到一个集合，涵盖了国家，如果这些点是圆心半径100英里所以像这样：
开始遍历列表，索引i=0。
找出列表中第i个点与列表中紧随其后的所有点之间的距离。
清除100英里内的任何点
重新索引数组
指数增加一
如果i=列表长度，结束，否则，循环

最佳答案

你的算法是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)。

关于algorithm - 想知道我的脚本的大O符号值(value)吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19324006/