这段代码和最大函数的时间复杂度是多少？

Question

对算法的这一部分中使用的操作数进行比较或乘法的操作数给出大O估计（忽略用于测试for循环中的条件的比较，其中a1，a2，... ，是一个正实数）。另外，max函数从索引'i'到'j'找到最大值，而不是只比较两个值。

m := 0
for i := 1 to n
  for j := i + 1 to n
    m := max(ai, aj, m)

该问题给出了max函数，没有描述。 function得到三个值，'ai'是起始索引，'aj'是end，'m'是变量来保存最大值。我认为函数的时间复杂度是O（n），因为'A'只是数组，我们必须遍历该部分才能获得最大值。我们想知道代码的bigO以及max函数。

Answer 1

首先，可以在没有通过数组的那么多迭代的情况下找到数组中的最大元素。您只需要一次通过并将m设置为高负数。

m := (highly negative number) -inf
for i := 1 to n
    m := max(ai,m)

对于您的算法，时间复杂度为O（n2），因为您不止一次地访问数组的不同部分，而不是如您所提到的那样。

更准确地说，算法的时间复杂度为：

（n-1）+（n-2）+（n-3）+ ... 1 = n * n - c（某些常数）

=> A（Na）