MAC 5741 - Introdução a Algoritmos e Arquiteturas
Paralelas
Lista de exercícios 1
(baseados nos livros de
Szwarcfiter, J. L. e Markenzon, L. Estruturas de Dados e seus
Algoritmos. LTC Editora, 1994 e
Ziviani, N. Projeto de Algoritmos com Implementações
em Pascal e C. Livraria Pioneira Editora, 1993.)
Escrever as seguintes funções em notação :
(a)
(b)
(c)
(d)
(e) 34
O que significa dizer que a função é ?
Dê a definição formal.
Indique se as afirmativas abaixo são verdadeiras ou falsas
e justifique sucintamente sua resposta.
(a)
(b)
Responder se é certo ou errado:
(a) Para um dado problema, se a complexidade do melhor caso
de um algoritmo é ,
então o limite inferior deste problema é
.
(b)
O limite inferior de um problema depende
só do problema.
(c) O limite inferior de um problema pode
mudar com a descoberta de um novo
algoritmo.
(d) O limite superior depende somente do
problema.
(e) O limite superior é sempre não inferior
ao limite inferior.