Quelle est la complexité temporelle de cet algorithme?

Question

Supposons que nous ayons un tableau w, qui contient n entiers. Par la définition suivante, et le pseudo code suivant, s'il vous plaît, dites-moi quelle est la complexité temporelle de l'algorithme 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

Vous avez 2 boucles ici -

1. boucle Première for loop des séries n fois. d'où son O (n).
2. La deuxième boucle while loop s'exécute à chaque fois à partir de (i-1) + (i-2) + (i-3) + .... + (i-n). il court (n-1) fois. Bientôt).

Combinaison à O(n^2) algo. Les autres opérations sont soit à temps constant, soit à temps O (n), donc négligées.