Arrays (Vetores)
Acesso Direto: Você pode acessar qualquer elemento instantaneamente se souber sua posição (índice). É como ir direto à número 5 para pegar algo - O(1)
Memória Contígua: Os elementos são armazenados um ao lado do outro na memória. Isso significa que precisamos definir o tamanho do array antecipadamente em muitas linguagens.
Inserção/Remoção: Pode ser custosa se não for no final do array, pois precisa mover todos os elementos subsequentes - O(n).
Listas Encadeadas
Nós Conectados: Cada elemento (nó) guarda dois valores: seu próprio dado e uma referência (endereço) para o próximo elemento.
Acesso Sequencial: Para encontrar um elemento, você precisa percorrer a lista desde o início, seguindo as referências - O(n)
Inserção/Remoção: Muito eficiente quando você já tem a posição, só precisa ajustar as referências - O(1)
Analogias e Complexidades de Arrays e Listas Encadeadas
Analogia do Mundo Real
Imagine uma fila de cinema:
- Array: Como cadeiras numeradas em uma sala - fácil encontrar a cadeira 15, mas difícil adicionar uma nova cadeira no meio.
- Lista Encadeada: Como uma fila de pessoas onde cada um segura o ombro da pessoa à frente - fácil adicionar alguém no meio, mas precisa contar desde o início para achar a 15ª pessoa.
Tabela de Complexidades
| Operação | Array | Lista Encadeada |
|---|---|---|
| Acesso | O(1) | O(n) |
| Inserção início | O(n) | O(1) |
| Inserção fim | O(1)* | O(n) |
| Remoção início | O(n) | O(1) |
| Remoção fim | O(1)* | O(n) |
| Busca | O(n) | O(n) |
algoritmos algoritmos_de_buscas
Conceito principal
A busca binária é um algoritmo que permite que ao passarmos como parâmetro uma lista ordenada e um numero, conseguimos identificar em que posição esse item está.
Descrição
Em resumo, para resolver ele utiliza do princípio de dividir para conquistar, ou seja, ele encontra o meio da lista, verifica se o número é maior ou menor que o elemento do meio. Caso seja maior, cria uma nova busca somente com números maiores, e repete o processo. Caso seja menor, cria uma nova busca somente com números menores.
Comentário: Informação não especificada no livro “Aprendendo Algoritmos”
Complexidade Temporal
O algoritmo possui a complexidade temporal O(log n), no pior caso, e O(1) no melhor caso. A complexidade O(log n) ocorre pois a cada iteração ele reduz o tamanho da lista pela metade, representando matematicamente:
- n / 2
- n / 4
- n / 8
- …
- k-ésima iteração: n / 2
No pior dos casos, isso leva a encontrar o item somente com um elemento:
Rearranjando a equação para resolver:
Assim, o número máximo de iterações é proporcional a:
Comentário: Informação não especificada no livro “Aprendendo Algoritmos”
Complexidade Espacial
A complexidade espacial da busca binária quando implementada de uma maneira não recursiva é O(1), ou seja, ocupa um espaço fixo, com base no tamanho da lista.