MAC 741 - 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.)

1. Escrever as seguintes funções em notação O:

   (a)

   (b)

   (c)

   (d)

   (e) 34

2. O que significa dizer que a função é ? Dê a definição formal.

3. Indique se as afirmativas abaixo são verdadeiras ou falsas e justifique sucintamente sua resposta.

   (a)

   (b)

4. 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.

• About this document ...