java - 说明此伪代码计算的内容并确定其运行时间

Question

这样的问题在我即将写的考试中可以问到。我在一本书中找到了这个，但遗憾的是没有解决方案。所以我解决了它，我希望你能告诉我我是否做对了？

a.) 算法计算什么？

b.) 根据n

分析算法的运行时间

     Input: Array A of length |A|=n with n >= 2
     Output: Number x
      x := 0;
      for i := 1 to n do
         for j := i+1 to n do
           if x < |A[i] - A[j]| then
              x := |A[i] - A[j]|;
           end if
         end for
      end for
      return x;

对于 a.) 我已经在 java 中将伪代码作为完整代码键入并执行了该程序。在对输出进行几次比较后，我意识到该算法计算了最小和最大的数组元素(如果需要，您可以在此处查看我的代码:https://gist.github.com/anonymous/b27877536f3c9f553500388af78ee962)

b.) 我不确定这是如何正确完成的，但我肯定也尝试过:

     Input: Array A of length |A|=n with n >= 2     O(1)
     Output: Number x
      x := 0;                                       O(1)
      for i := 1 to n do                            O(n)
         for j := i+1 to n do                      *O(n)
           if x < |A[i] - A[j]| then               *O(1)
              x := |A[i] - A[j]|;                  *O(1)
           end if                                  *O(1)
         end for                                   *O(1)
      end for                                      *O(1)
      return x;                                     O(1)
                                                  = O(n*n) = O(n^2)

Answer 1

您在A 部分 中的答案:不正确，因为|A[i] - A[j]| 表示绝对值而不是阶乘。例如:|1-3| = 2。因此，该算法计算数组值之间的最大差异。

在Part B中，你是对的，它是O(n^2)，它被称为二次方，你可以找到更多信息here .