java algorithms collections

Algoritmos y colecciones de Java

Recopilación personalizada de datos para entrevista técnica para el rol de desarrollador de Java Junior.

Algoritmos

Ver lista completa aquí

Big O notación

• Complejidad del tiempo : estimación del número de operaciones o pasos que un algoritmo debe ejecutarse en función del tamaño de entrada.
• Complejidad del espacio : cantidad máxima de memoria auxiliar que un algoritmo necesita asignar o usar durante su ejecución en función del tamaño de entrada.
  • El espacio auxiliar es el espacio adicional o el espacio temporal utilizado por un algoritmo.

n En la complejidad del tiempo: el número de elementos en la entrada.

n en complejidad del espacio: tamaño de entrada en unidades de bits necesarios para representar la entrada.

Mesa de complejidad de tiempo grande

Tipo	Nombre	Explicación	Estado	Ejemplo
O(1)	Tiempo constante	El algoritmo se ejecuta el mismo número de veces cada vez, independientemente del tamaño de la entrada	Excelente	Buscar en una tabla hash por clave
O(log n)	Tiempo de logaritmo	El tiempo de ejecución aumenta muy lentamente en comparación con el aumento en el tamaño de los datos de entrada	Excelente	Búsqueda binaria (promedio)
O(n)	Tiempo lineal	El tiempo de ejecución es linealmente proporcional al tamaño de los datos de entrada	Bien	Búsqueda de fuerza bruta
O(n + k)	Tiempo combinado/aditivo	Complejidad combinada de dos entradas separadas	Bien	Clasificación de contabilidad
O(n log n)	Tiempo cuasilíneo	A medida que aumenta el tamaño de la entrada, el número de divisiones requeridas para resolver el problema aumenta lentamente debido al crecimiento logarítmico	Malo	Sorteo de fusión, clasificación de montón
O(n^2)	Tiempo cuadrático	Implica iteraciones o comparaciones anidadas para cada elemento	Horrible	Clasificación de selección
O(2^n)	Tiempo exponencial	Implica una búsqueda o enumeración exhaustiva de todas las combinaciones posibles de la entrada, el tiempo de ejecución aumenta exponencialmente	Horrible	TSP (programación dinámica)
O(n!)	Tiempo factorial	Implica una búsqueda o enumeración exhaustiva de todas las combinaciones posibles de la entrada, el tiempo de ejecución aumenta factorialmente	Horrible	TSP (fuerza bruta)

Mesa de complejidad espacial Big-O

Tipo	Nombre	Explicación	Estado	Ejemplo
O(1)	Espacio constante	El algoritmo requiere una cantidad fija de memoria adicional, independientemente del tamaño de entrada	Excelente	Sort de montón
O(log n)	Espacio logarítmico	El uso del espacio aumenta lentamente en comparación con el aumento en el tamaño de los datos de entrada	Excelente	Clasificación rápida
O(n)	Espacio lineal	El uso del espacio escala linealmente con el tamaño de entrada	Bien	Fusionar
O(n + k)	Espacio combinado/aditivo	El uso del espacio escala linealmente con la suma de n y k	Malo	Radix Sort

Definiciones

Término	Definición	Ejemplos
Tipo de datos abstracto (ADT)	Representa una descripción de alto nivel de un tipo de datos, centrándose en su comportamiento y operaciones en lugar de los detalles de implementación específicos	pila, cola, diccionario, secuencia, set
Estructura de datos	Técnica o estrategia para implementar un tipo de datos particular, organizar y almacenar datos de una manera específica para facilitar operaciones eficientes	matriz, lista vinculada, tabla hash, árboles (árbol de búsqueda binario, montón, árboles rojos/negros

Clases de colecciones de Java

• Recopilación
  • Colocar
    • Hashset
    • Linkedhashset
      • Mortero
      • Navegar
        • Árbol de árboles
  • Lista
    • Lista de matriz
    • Linkedlist
    • Vector
      • Pila
  • Cola
    • Cola prioritaria
      • Deparar
        • Arraydequeue
• Mapa
  • Hashtable
  • Mapache
  • Linkedhashmap
    • Mapa mortista
    • Navegación
      • Treemap

Comparación de tipos de recolección:

Tipo	Elementos duplicados	Orden de elementos	Debe agregar/eliminar en orden específico
Lista	Permitido	Por índice	No
Mapa	Permitido para valores	Java usa el hashcode () de la clave para determinar el orden, para nosotros no está ordenado	No
Cola	Permitido	Recuperado en orden definido	Sí
Colocar	Prohibido	Solo en TreeSet	Sí

Atributos de colección:

Tipo	Interfaz	Ordenado?	Llama hashCode() ?	Llama compareTo() ?
Lista de matriz	Lista	No	No	No
Linkedlist	Lista, Deque	No	No	No
Arraydeque	Cola, deque	No	No	No
Hashset	Colocar	No	Sí	No
Árbol de árboles	Establecer, sortedset	Sí	No	Sí
Linkedhashset	Colocar	No	Sí	No
Mapache	Mapa	No	Sí	No
Linkedhashmap	Mapa	No	Sí	No
Treemap	Mapa, Sortedmap	Sí	No	Sí

Las estructuras de datos que implican la clasificación no permiten valores nulos.