Blog

FACULDADE ANHANGUERA DE TAUBATÉ – UNIDADE II Análise e Complexidade de Algoritmos Prof. Fernando Salles Claro Atividade Prática Supervisionada Curso: Ciência da Computação Semestre: 10 – Turma A- Ano: 2012/1 Etapa 1 OF4 p Melhor Caso * Definido pela letr * Exprime o menor tempo de execução de um algoritmo para uma entrada de tamanho n. * Ex: Pior Caso * Representado pela letra grega O (Ómicron). * Baseia-se no maio tempo de execução sobre todas as entradas de tamanho n. * É o método mas fácil de se obter. Caso Médio * Definida pela letra grega e(Theta) o g(n) c2 (n) Crie um Algoritmo.

Procedure Verifica Item Lista (Lista: TipoLista; x: Tipoltem; pos: integer); Var i: integer; Begin achou false; While (i <= Lista. Tamanho) and not achou do begin I nc(i); if Lista. lntem[i] then achou :- true; end; if achou then pos pos -1; Etapa 2 Cite as vantagens e desvantagens dos algoritmos de ordenação por seleção e de ordenação por inserção. * ordenaçao por seleçao (SECTION SORT) É um algoritmo que ordena itens verificando repetidamente os itens restantes para encontrar o menor deles e movê-lo para uma posição final. A idéia por trás do selection sort é que para ordenar N itens você tem que passar por todos eles. . No primeiro passo você encontra o maior valor, e então troca ele pelo último item. Assim o maior item está agora na posição N. vez e colocá-lo na frente. Para ordenar em ordem decrescente, o maior item é encontrado a cada vez e movido para a frente. Pior e melhor caso: O(n2) * Ordenação por Inserção (INSERTION SORT) É um algoritmo eficiente para ordenar um pequeno número de elementos. Basicamente, este algoritmo varre um array de elementos da esquerda para a direita e a medida que avança vai deixando os elementos mais a esquerda ordenados. Melhor caso: quando o array já está ordenado.

Neste caso a comparação no laço interno sempre falhará na primeira comparação e o tempo de execução dependerá apenas do laço externo. O tempo de execução obedecerá a uma função linear e a complexidade do algoritmo será de O(n). Pior caso: quando o array está na ordem inversa. Nesta situação para cada iteração do laço externo, o laço interno executará n-l vezes, onde n é o valor da variável j no laço externo. Temos que a complexidade de tempo do algoritmo neste caso será de = O(n2-n) = O(n2). Crie um algoritmo de ordenação por inserção e um de ordenaçao or seleção. Ordenação por Inserção (Insertion Sort) 1 vold insertion(int v[], Int n) { 2 3 4 5 6 7 int i, j, x; ;j<n;j++) { o(n) 0(1) for(i=j-l;i >=O && v[l]>x;–i) v[i+l] V[i]; 3 v[i]>x;–i) v[i+l] VI] 8 v[i+l] x, )+o(n)+o(l )+o(l) n2+3 é uma função quadrática. * Ordenação por Seleção (Selection Sort) 9 10 11 12 13 void selectionSort(int vetor[],int tam int i,j; int min,aux; for ;i++){ min=i; for (j=i+l ;j<tam;j++){ if min=j; } vetor[i]=vetor[min]; o(tam) 0(0) o(o) )+o(l) )+o(l )+o(tam)+o(tam) =5 +tam2 5+tamR é uma função quadrática. 4DF4