PRATICA-01

Prévia do material em texto

Prof. Ricardo M. Marcacini
Algoritmos e Programação II
LISTA DE EXERCÍCIOS 1
Eficiência de Algoritmos e Notação O
Exercício 1) Considere a função de complexidade de três algoritmos A, B e C. Plote as 
seguintes funcões e observe (aproximadamente) quando uma supera a outra em termos 
do número de operacões de acordo com o tamanho da entrada n: 
• Algoritmo A → 1000*n 
• Algoritmo B → 0,1*n²
• Algoritmo C → 5000*log n
Exercício 2) Sejam dois algoritmos A e B. Sabe-se que algoritmo A realiza 2n² operações 
e que o algoritmo B realiza 50 log n operações. Sabendo que n é um inteiro em que
n >= 1, para quais valores de n: 
• O algoritmo A gera menos operações que B? 
• O algoritmo B gera menos operações que A?
Exercício 3) Escreva as seguintes funções em notação O e, em seguida, classifique-as 
por ordem de crescimento: 
(a) n³ − n 
(b) n² + 2 log n 
(c) 3n + 5 
(d) 3n + 10n 
(e) (3,2)n 
(f) 302 
(g) n log n 
(h) n² + n log n 
(i) (42,35)n+2n 
(j) 8n + 4n² 
(k) 1054 
(l) n log n + n 
(m) n³ + n + n⁴
(n) 100 + 2n
Exercício 4) Pesquise (em livros e/ou internet) um problema da computação para as 
principais classes de problemas:
• O(1)
• O(log n)
• O(n)
• O(n log n)
• O(n²)
• O(n³)
• O(2n)
• O(n!)