Seja V um vetor contendo n elementos distintos. a. Determine o numero exato de comparaçoes entre elementos (em função de n) que o algoritmo de ordenacao por selecao realiza para ordenar V . b. Determine o numero exato de trocas entre elementos (em funcao de n) que o algoritmo de ordenacao por selecao realiza para ordenar V , no caso em que os elementos de V encontram-se em ordem decrescente. c. Utilize a notacao O para representar os valores obtidos nos itens (a) e (b).
Para determinar o número exato de comparações entre elementos que o algoritmo de ordenação por seleção realiza para ordenar um vetor V com n elementos distintos, podemos usar a fórmula matemática (n-1) + (n-2) + ... + 1. Isso ocorre porque, no primeiro passo, comparamos o primeiro elemento com os n-1 elementos restantes. No segundo passo, comparamos o segundo elemento com os n-2 elementos restantes, e assim por diante. Portanto, o número exato de comparações é dado pela soma dos números de 1 a n-1, que pode ser calculada pela fórmula n*(n-1)/2. Para determinar o número exato de trocas entre elementos que o algoritmo de ordenação por seleção realiza para ordenar o vetor V no caso em que os elementos estão em ordem decrescente, podemos usar a mesma fórmula (n-1) + (n-2) + ... + 1. Isso ocorre porque, em cada passo, selecionamos o menor elemento restante e o trocamos com o elemento na posição atual. Portanto, o número exato de trocas também é dado pela soma dos números de 1 a n-1, que pode ser calculada pela fórmula n*(n-1)/2. Utilizando a notação O, podemos dizer que o número exato de comparações e trocas no algoritmo de ordenação por seleção é O(n^2), pois a fórmula n*(n-1)/2 pode ser simplificada para n^2/2, e a notação O ignora constantes e termos de menor ordem.
Para escrever sua resposta aqui, entre ou crie uma conta
Compartilhar