Aprender algoritmos

Capítulo 8. Embrulha tudo

Este trabalho foi traduzido com recurso a IA. Agradecemos o teu feedback e comentários: [e-mail]

O meu objetivo neste livro foi apresentar-te os algoritmos fundamentais e os tipos de dados essenciais utilizados na ciência da computação. Precisas de saber como implementar eficientemente os seguintes tipos de dados para maximizar o desempenho do teu código:

Saco

Uma lista ligada garante um desempenho O(1) quando adiciona um valor. Se optar por usar um array, então precisa de empregar um redimensionamento geométrico para aumentar o tamanho do array de modo a garantir um desempenho O(1) amortizado durante a sua utilização média (embora continue a incorrer num desempenho O(N) em tempo de execução nos eventos de redimensionamento pouco frequentes). Nota que um saco não permite tipicamente a remoção de valores, nem impede a adição de valores duplicados.

Empilha

Uma lista ligada pode armazenar os valores numa pilha, pelo que push() e pop()têm um desempenho de tempo de execução O(1). A pilha regista o top da pilha para empurrar e retirar valores.

Fila de espera

Uma lista ligada pode armazenar eficientemente uma fila, pelo que enqueue() edequeue() têm um desempenho de tempo de execução O(1). A fila regista o nó first e o nó last na lista ligada para adicionar e remover valores da fila de forma eficiente.

Tabela de símbolos

A abordagem de endereçamento aberto para tabelas de símbolos é surpreendentemente eficiente, com funções hash ...