Estruturas de Dados
O estudo de estruturas de dados, um componente fundamental da educação em ciência da computação, serve como base sobre a qual muitos outros campos da ciência da computação são construídos. O conhecimento desse campo, das estruturas de dados, é de importância para os estudantes que desejam trabalhar no desenvolvimento de projetos, implementação, teste ou manutenção de praticamente qualquer sistema de software. Nosso repositório conta com a implementação de algumas dessas estruturas de dados, para mais informações:
- Listas
- Filas
- Pilhas
- Grafos e Árvores
- Tabela Hash
Complexidade assintótica das estruturas de dados
A tabela abaixo resume a complexidade de tempo de operações e de uso de memória para as principais estruturas de dados. Para obter mais detalhes sobre esse assunto, leia a seção Complexidade Assintótica.
| Estrutura de dados | Complexidade de tempo | Complexidade espacial | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Caso médio | Pior caso | Pior caso | |||||||
| Acesso | Busca | Inserção | Remoção | Acesso | Busca | Inserção | Remoção | ||
| Array | Θ(1) | Θ(n) | Θ(n) | Θ(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
| Lista | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Fila | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Pilha | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Árvore BST¹ | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Árvore AVL² | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | Θ(log(n)) | O(n) |
| Árvore B³ | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Tabela hash | N/A | Θ(1) | Θ(1) | Θ(1) | N/A | O(n) | O(n) | O(n) | O(n) |
¹ Árvore Binária de Busca (BST - Binary Search Tree).² Árvore do tipo balanceada (AVL - Adelson-Velsky and Landis).³ Generalização da árvore BST.