java algorithms collections

Algoritmos e coleções Java

Coleção personalizada de dados para entrevista técnica para o papel júnior do desenvolvedor Java.

Algoritmos

Veja toda a lista aqui

Grande notação o

• Complexidade do tempo : estimativa do número de operações ou etapas que um algoritmo precisa ser executado em função do tamanho da entrada.
• Complexidade do espaço : quantidade máxima de memória auxiliar que um algoritmo precisa alocar ou usar durante sua execução em função do tamanho da entrada.
  • O espaço auxiliar é o espaço extra ou o espaço temporário usado por um algoritmo.

n Na complexidade do tempo - o número de elementos na entrada.

n na complexidade do espaço - tamanho de entrada em unidades de bits necessárias para representar a entrada.

Tabela de complexidade do tempo grande

Tipo	Nome	Explicação	Status	Exemplo
O(1)	Tempo constante	O algoritmo é executado o mesmo número de vezes a cada vez, independentemente do tamanho da entrada	Excelente	Pesquise em uma tabela de hash por chave
O(log n)	Tempo do logaritmo	O tempo de execução aumenta muito lentamente em comparação com o aumento do tamanho dos dados de entrada	Excelente	Pesquisa binária (média)
O(n)	Tempo linear	O tempo de execução é linearmente proporcional ao tamanho dos dados de entrada	Bom	Pesquisa de força bruta
O(n + k)	Tempo combinado/aditivo	Complexidade combinada de duas entradas separadas	Bom	Contagem de classificação
O(n log n)	Tempo de Quasilinear	À medida que o tamanho da entrada aumenta, o número de divisões necessárias para resolver o problema aumenta lentamente devido ao crescimento logarítmico	Ruim	Merge classificar, tipo de heap
O(n^2)	Tempo quadrático	Envolve iterações ou comparações aninhadas para cada elemento	Horrível	Classificação de seleção
O(2^n)	Tempo exponencial	Envolve pesquisa exaustiva ou enumeração de todas as combinações possíveis da entrada, o tempo de execução aumenta exponencialmente	Horrível	TSP (Programação Dinâmica)
O(n!)	Tempo fatorial	Envolve busca exaustiva ou enumeração de todas as combinações possíveis da entrada, o tempo de execução aumenta fatorialmente	Horrível	TSP (força bruta)

Tabela de complexidade espacial Big-O

Tipo	Nome	Explicação	Status	Exemplo
O(1)	Espaço constante	O algoritmo requer uma quantidade fixa de memória adicional, independentemente do tamanho da entrada	Excelente	Classificação da pilha
O(log n)	Espaço logarítmico	O uso de espaço aumenta lentamente em comparação com o aumento do tamanho dos dados de entrada	Excelente	Classificação rápida
O(n)	Espaço linear	O uso de espaço escala linearmente com o tamanho da entrada	Bom	Mesclar classificar
O(n + k)	Espaço combinado/aditivo	O uso espacial escala linearmente com a soma de n e k	Ruim	Radix Sort

Definições

Prazo	Definição	Exemplos
Tipo de dados abstrato (ADT)	Representa uma descrição de alto nível de um tipo de dados, concentrando-se em seu comportamento e operações, em vez dos detalhes específicos da implementação	pilha, fila, dicionário, sequência, conjunto
Estrutura de dados	Técnica ou estratégia para implementar um tipo de dados específico, organizando e armazenando dados de uma maneira específica para facilitar operações eficientes	Array, lista vinculada, tabela de hash, árvores (árvore de pesquisa binária, pilha, árvores vermelhas/pretas

Aulas de coleções Java

• Coleção
  • Definir
    • Hashset
    • LinkedHashSet
      • STORDEDSET
      • Navigableset
        • Treeset
  • Lista
    • Arraylist
    • LinkedList
    • Vetor
      • Pilha
  • Fila
    • Fila de prioridade
      • Deque
        • Arraydequeue
• Mapa
  • Hashtable
  • Hashmap
  • LinkedHashmap
    • SortedMap
    • NAVIGABLEMAP
      • Treemap

Comparando tipos de coleção:

Tipo	Elementos duplicados	Ordem dos elementos	Deve adicionar/remover em ordem específica
Lista	Permitido	Por índice	Não
Mapa	Permitido para valores	Java usa o hashcode () da chave para determinar a ordem, pois não é classificado	Não
Fila	Permitido	Recuperado em ordem definida	Sim
Definir	Entrada	Somente em Treeset	Sim

Atributos da coleção:

Tipo	Interface	Classificado?	CHAMADA hashCode() ?	Chama compareTo() ?
Arraylist	Lista	Não	Não	Não
LinkedList	Lista, deque	Não	Não	Não
Arraydeque	Fila, deque	Não	Não	Não
Hashset	Definir	Não	Sim	Não
Treeset	Conjunto, SortedSet	Sim	Não	Sim
LinkedHashSet	Definir	Não	Sim	Não
Hashmap	Mapa	Não	Sim	Não
LinkedHashmap	Mapa	Não	Sim	Não
Treemap	Mapa, SortedMap	Sim	Não	Sim

As estruturas de dados que envolvem classificação não permitem valores nulos.