algorithm - 朴素算法的最坏情况运行时间

Question

我不确定如何计算算法的最坏情况运行时间。我熟悉渐近符号，但不确定如何使用它。一个解释的例子可以是:

d = (X1 - X2)^2 + (Y1 - Y2)^2
for i=1 to N-1 do:
  for j=i+1 to n do:
     t = (Xi - Xj)^2 + (Yi - Yj)^2
     if (t < d) then d = t
return d

这有一组 N 个点 (X1,Y1)....(XN,YN) 的输入，其中 N>=2。输出应该是最近的一对点的平方距离。我如何计算它的运行时间？

Answer 1

该算法从 N 个输入中获取所有可能的对。有n(n-1)/2这样的对，也就是内层循环执行的次数。假设算术运算在时间上是常数，那么时间复杂度是 O(n²)。

请注意，此算法中没有影响时间复杂度的未知因素，因此这是最好和最坏情况下的时间复杂度:θ(n²)