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. 2番目のループwhile loopはから毎回実行され(i-1) + (i-2) + (i-3) + .... + (i-n)ます。（n-1）回実行されます。すぐ）。

O(n^2)アルゴに結合します。他の操作は一定時間またはO（n）時間のいずれかであるため、無視されます。