Boa noite pessoal, tudo bem?
Preciso de uma ajuda meio urgente: vou ter uma entrevista para enginer da Amazon, e gostaria de saber algumas coisas sobre estruturas de dados.
Fiz o curso aqui da alura, implementei todas. Mas ainda tenho algumas dúvidas:
por exemplo a complexidade de uma lista ligada para um vetor.
Como tenho deficiência visual, o único bom material que eu encontrei foi aqui no alura; os outros materiais são um monte de vídeo e imagem e não consigo entender.
No caso, eu queria entender mais essa questão da complexidade.
Entendo que o(1) é tempo constante, o(n) é tempo linear.
Mas eu não sei classificar o que seria o que.
Por exemplo: eu queria entender se as operações em um HASHSET, em uma lista ligada, em uma lista duplamente ligada e em uma árvore de busca binária teria qual complexidade...
Se alguém me perguntar isso na entrevista, não faço ideia de como pensar pra responder.
Tirando adicionar no começo e no fim, remover no começo e no fim de uma lista duplamente ligada, acessar uma posição de um array... O resto tudo parece linear.
Conseguem me ajudar por favor?
1
resposta
resposta
Ajuda urgente com complexidade
Oi Maurilio, tudo bem?
Peço desculpas pela demora em obter retorno, principalmente porque se tratava de algo urgente.
Vou exemplificar com a lista ligada. Operações de adicionar, remover e buscar um elemento específico têm custo O(n), isso porque precisamos, no pior caso, percorrer os n elementos da lista para encontrar esse elemento e realizar a operação. Agora, para retornar o primeiro elemento de uma lista, só pegamos o atributo elemento da lista encadeada e realizamos a operação, sem precisar percorrê-la. Por isso, ela tem custo O(1). Fazendo uma definição bem simples, toda vez que precisamos percorrer toda uma estrutura, o custo deixa de ser constante e passa a ser do tamanho da estrutura.
Em listas duplamente ligadas, esse custo ainda é o mesmo.
Com relação à árvore, esse custo de percorrer a estrutura até encontrar um nó específico passa a ser O(log n) - se a árvore está balanceada - , por ela se dividir em várias e não precisarmos passar por todos os nós.
Espero ter ajudado, abraços!
Caso este post tenha lhe ajudado, por favor, marcar como solucionado ✓. Bons Estudos!