Estrutura de Dados - Complexidade de Algoritmos (Exercícios Resolvido)

UNISUL – Universidade do Sul de Santa Catarina

Curso de Ciência da Computação

Disciplina de Estrutura de Dados

Professor Luciano Savio

Aula 2

Lista de Exercícios 2

Defina a equação de complexidade para os algoritmos nas situações de MELHOR e de PIOR caso além de expressar a complexidade simplificada na notação big-oh (O)

1)

Entrada: n

i ← n                                1

y ← 1                                1

Enquanto i > 0 Faca        n + 1

y ← y ∗ i                2n

i ← i – 1                2n

Fim Enquanto

Retornar y                        1

RESPOSTA: 4 para melhor caso (n=0)

5n+4 pior caso.

O(n)

2)

Entrada: x: chave; lista tab : vetor[1. . . n];

Saıda: pos: posicao do elemento na lista tab

                                                Pior        Melhor

i ← 0                                                1        1

achou ← F                                        1        1

Repita                                                

i = i + 1                                2n        2

Se tab[i] = x Entao                        2n        2

achou = V                        0        1

Fim Se

Ate achou = V ou i = n                        2n         1

Se achou Entao                                1        1

pos ← i                                0        1

Fim Se

Retornar pos                                1        1

RESPOSTA:

Pior Caso: 6n+4 (quando não encontra x)

O(n)

Melhor Caso: 11 (encontra x na 1ª. Pos do vetor)

O(1)

3)

Entrada: Tabela tab : vetor[1. . . n]

Saıda Mx = valor maximo em tab        Pior                Melhor

Mx ← tab[1]                                2                2

Para i de 2 ate n Faca                        1+n+n-1        1+n+n-1

Se Mx ≤ tab[i] Entao                2(n-1)                2(n-1)

Mx ← tab[i]                        2(n-1)                0

Fim Se

Fim Para

Retornar Mx                                1                1

Pior Caso: 6n-1

Melhor Caso: 4n+1

O(n)

4)

Entrada: Tabela T : vetor[1. . . n]        Pior                Melhor

Para i de 1 ate n − 1 Faca                        1+n+n+n-1        1+n+n+n-1        

minj ← i                                n-1                n-1

...