3.10. Exercícios de Programação¶

1. Faça um experimento para verificar que o acesso a um elemento através de seu índice em uma lista é \(O(1)\).

2. Faça um experimento para verificar que o acesso e atribuição a um item de um dicionário é \(O(1)\).

3. Faça um experimento para comparar a performance do operador del em listas e dicionários.

4. Dada uma lista de números em ordem aleatória, escreva um algoritmo que funcione em \(O(n\log(n))\) para achar o k-ésimo menor número da lista.

5. Você pode melhorar o algoritmo do problema anterior para que ele seja linear? Explique.