이 알고리즘의 시간 복잡도 란 무엇입니까?

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^2) algo에 결합합니다. 다른 작업은 일정 시간 또는 O (n) 시간이므로 무시됩니다.