Escreva um algoritmo que receba um vetor ordenado e um número extra e insira esse número na sua posição correta no vetor ordenado, deslocando os outros números se necessário. Quais são sua função de custo e ordens de complexidade O e Omega ?

Passo 1

O enunciado pede um algoritmo que, dado um vetor já ordenado de tamanho n e um elemento extra x, insira x na posição correta, deslocando os demais elementos. Vamos tratar de análise de custo (função C(n)) e das ordens de complexidade O e Ω.

Passo 2

Um esboço do algoritmo em alto nível é: 1) Percorrer o vetor da esquerda para a direita até encontrar a primeira posição i tal que vetor[i] ≥ x (ou chegar ao fim). 2) Deslocar todos os elementos de índice ≥ i uma posição para a direita, começando de n–1 até i. 3) Colocar x em vetor[i].

Passo 3

Para a função de custo C(n), contamos duas operações principais: comparações durante a busca do índice i e deslocamentos dos elementos. Se x deve ficar na posição k (0 ≤ k ≤ n), o número de comparações será k+1 (ou n se chegar ao fim) e o número de deslocamentos será n–k. Assim:
C(n,k) = (k+1) + (n - k) = n + 1

Passo 4

No melhor caso x é maior que todos os elementos (k = n), temos C(n,n) = n+1+0 = n+1 ∈ Ω(1) (no sentido de crescimento constante, pois quando n cresce, inserção no fim exige só uma comparação e atribuição).
No pior caso x é menor que todos (k = 0), temos C(n,0) = 1 + n = n+1 ∈ O(n).

Passo 5

Logo, a ordem de complexidade do algoritmo é O(n) no pior caso e Ω(1) no melhor caso.

Resposta

Função de custo aproximada: C(n)=n+1. Complexidade: O(n) no pior caso, e Ω(1) no melhor caso.

Exercícios relacionados