analiSe e complex

Centro Universitário do Sul de Minas – UNIS-MG
Unidade de Gestão da Educação Superior Presencial – GEP
Ciência da Computação

Complexidade de Algoritmos Insertion, Selection e Bubble Sort
Análise de Algoritmos

Professor Renan Levenhagen Bustamante Neves

Júlio Cezar Ferreira Rocha

Varginha
2013

1 - Complexidade de Algoritmos Bubble Sort

As operações de comparações e de troca de posição de elementos são executadas no Pior Caso, o algoritmo realizará n-1 troca para o primeiro passo, depois n-2 trocas para o segundo elemento e assim sucessivamente. Trocas = n-1+n-2+n-3...+2+1 aproximadamente n2 trocas. No Melhor Caso, nenhuma troca será realizada, pois em ambos os casos o algoritmo faz da ordem n comparações.

Complexidade no tempo: Comportamento do algoritmo no tempo, em função do tamanho da entrada.
Complexidade no espaço: Consumo de memória do algoritmo, em função do tamanho da entrada.

O tempo gasto na execução do algoritmo varia em ordem quadrática em relação ao número de elementos a serem ordenados.
- T = O (n²) – Notação “Big O”
- Atividades mais custosas:
Comparações
Troca de Posição (swap)

Melhor caso: Vetor Ordenado.
Pior caso: Vetor invertido.

2 - Complexidade de Algoritmos Selection Sort

A operação entre as chaves é feita no loop k, para cada valor de i são realizadas (i-1) comparações no loop, como i varia de 2 até n, o número tota l de comparações para ordenar a lista toda é que para qualquer valor de i existe no máximo uma troca, se no caso a lista já estiver ordenada não ocorre troca. Pior caso existe uma troca para cada loop de k (n-1) para cada troca exige três movimentos. O algoritmo de seleção é considerado um dos mais simples, além disso, possui uma característica eficiente quanto à quantidade de movimentações de registros, com um tempo de execução linear no tamanho de entrada. Geralmente é utilizado para arquivos de registros maiores com até 1000