algorithm - 这个算法的时间复杂度是多少？

Question

假设我们有一个w包含n整数的数组。请通过以下定义和以下伪代码告诉我算法 wrt 的时间复杂度是多少n：

idx[i] = max(j) : 1 <= j < i and w[j] < w[i]

alg:
Data: w : array of integers - idx: a pointer to maximum index with the less value.
Date: w is 1based

idx[1] = -1
for i=: 2 to n do
  j=i-1
  while w[j] > w[i] and j <> -1
  {
    j = idx[j]
  }
  idx[i] =j
end

Answer 1

你这里有 2 个循环 -

1. 第一个循环for loop运行 n 次。因此它的 O(n)。
2. 第二个循环while loop每次从 运行(i-1) + (i-2) + (i-3) + .... + (i-n)。它运行（n-1）次。很快）。

结合O(n^2)算法。其他操作要么是常数时间，要么是 O(n) 时间，因此被忽略。