Algoritmo de mediana e indice remissivo

845 palavras 4 páginas
Centro Federal de Educação Tecnológica de Minas Gerais
Laboratório de Algoritmos e Estruturas de Dados I

Prática 1: O objetivo dessa prática é fazer o cálculo da mediana entre três números inteiros. Para fazer esse cálculo utilizamos um algoritmo para determinar a ordem entre os três números informados, dessa a mediana será o número de valor intermediário dessa lista. Entretanto, como o número de entradas é sempre igual a três, não é necessário o uso de uma lista (vetor) para realizar a ordenação dos três números dados. Sejam as três entradas do algorítimo os números inteiros A, B e C. A orenação dos números é dada de acordo com a árvore de decisão abaixo:

Analisando a árvore de decisão do algoritmo podemos observar que, no melhor caso, o algoritmo realiza duas comparações, e em seu pior caso ele realiza três comparações. Desta forma podemos perceber ainda a vantagem desse tipo de implementação (para o caso de três entradas) em relação ao uso de uma lista com um algoritmo de ornedação simples, pois esse tipo de implementação geralmente aprensenta um custo de O(n²) o que leva a um número de comparações três vezes maior do que o pior caso do algorítimo apresentado.

Implementação: public static int CalcularMediana(int n1, int n2, int n3)
{
int intMediana = 0; if(n1 > n2) { if(n2 > n3) intMediana = n2; else { if(n1 > n3) intMediana = n3; else intMediana = n1; } } else { if(n2 > n3) { if(n1 > n3) intMediana = n1; else intMediana = n3; } else intMediana = n2; }

return intMediana;
}

Melhor e pior caso:
Melhor Caso: O(2)
Pior Caso: O(3)

Caso médio:
Para calcular o caso médio foi feita a medição da frequência do número de comparações para 1000 execuções do algoritmo. Os resultados dessa medição se encotram na tabela abaixo:

Duas Comparações
Três Comparações
334
666 De acordo com a tabela acima podemos perceber que o caso

Relacionados

  • Projetos de algoritmos
    42029 palavras | 169 páginas
  • Instruções TI 83
    14154 palavras | 57 páginas
  • avan ado em c
    11477 palavras | 46 páginas
  • vaso cu
    67326 palavras | 270 páginas
  • cronograma
    67326 palavras | 270 páginas
  • Primeiros socorros
    23464 palavras | 94 páginas
  • Relatório de estagio segurança do trabalho
    10457 palavras | 42 páginas
  • Trabalho de conclusão de curso
    10931 palavras | 44 páginas
  • Manual de 1º. socorros
    18490 palavras | 74 páginas
  • Scilab livro
    35539 palavras | 143 páginas