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

Question

假设我们有一个数组w，其中包含n整数。通过下面的定义和下面的伪代码，请告诉我什么是算法w.r.t的时间复杂性。 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）。

合并到O(n^2)算法。其他操作要么是恒定时间，要么是O（n）时间，因此被忽略。