Escreva um algoritmo que receba valores em um vetor e imprima “ORDENADO” se o vetor estiver em ordem crescente. Qual é função de custo de pior caso e sua ordem de complexidade
?
Passo 1
O exercício pede um algoritmo que recebe um vetor de tamanho
e imprime “ORDENADO” se o vetor estiver em ordem crescente. O conteúdo envolve verificação de ordenação e análise de custo, e vamos precisar contar quantas comparações de elementos adjacentes são feitas.
Passo 2
A estratégia é percorrer o vetor do segundo elemento até o último, comparando cada elemento com o seu antecessor. Se em alguma dessas comparações encontrarmos um valor menor que o anterior, concluímos que o vetor não está ordenado e podemos terminar a execução. Caso nenhuma dessas comparações falhe, imprimimos “ORDENADO”.
Em pseudocódigo fica assim:
for i de 1 até n-1:
se vetor[i] < vetor[i-1] então
retorne // vetor não está ordenado
fim do for
imprime “ORDENADO”
Em pseudocódigo fica assim:
for i de 1 até n-1:
se vetor[i] < vetor[i-1] então
retorne // vetor não está ordenado
fim do for
imprime “ORDENADO”
Passo 3
No pior caso, o vetor já está ordenado e, portanto, todas as comparações de pares adjacentes serão efetuadas. Há exatamente
pares adjacentes em um vetor de tamanho
, logo realizamos
comparações.
Dessa forma, a função de custo de pior caso é . Na notação assintótica, desprezamos constantes e termos de ordem inferior, ficando a complexidade como
.
Dessa forma, a função de custo de pior caso é
Resposta
A função de custo de pior caso é
e a ordem de complexidade é
.