Algoritmo O(n²) em O(n) , c/ Estrutura de Pilha

fscfelipe
(usa Ubuntu)

Enviado em 18/03/2015 - 01:21h

Preciso de uma luz para conseguir transformar esse algoritmo em O(n), utilizando uma pilha

ele pega um vetor de valores inteiro, percorre a partir do ultimo ao primeiro, e cada valor[j] que o número da vez[i] encontrar menor do que ele, soma-se +1 ao indice de somas S[i]., e quando encontrar um maior, breaka o segundo para, e passa para o próximo valor da vez[i]

para i de n até 0 faça

  para j de i-1 até 0 faça

     se Pi > Pj então

            S[i] = S[i] + 1

     senão

            break