java algorithms collections

Algorithmes et collections Java

Collecte personnalisée de données pour un entretien technique pour le rôle de développeur Java junior.

Algorithmes

Voir la liste entière ici

Big O Notation

• Complexité temporelle : estimation du nombre d'opérations ou étapes qu'un algorithme doit s'exécuter en fonction de la taille de l'entrée.
• Complexité de l'espace : quantité maximale de mémoire auxiliaire qu'un algorithme a besoin pour allouer ou utiliser pendant son exécution en fonction de la taille d'entrée.
  • L'espace auxiliaire est l'espace supplémentaire ou l'espace temporaire utilisé par un algorithme.

n dans la complexité du temps - le nombre d'éléments dans l'entrée.

n dans la complexité de l'espace - Taille d'entrée dans les unités de bits nécessaires pour représenter l'entrée.

Table de complexité du temps grand

Taper	Nom	Explication	Statut	Exemple
O(1)	Temps constant	L'algorithme est exécuté le même nombre de fois à chaque fois, quelle que soit la taille de l'entrée	Excellent	Rechercher dans une table de hachage par clé
O(log n)	Temps de logarithme	Le temps d'exécution augmente très lentement par rapport à l'augmentation de la taille des données d'entrée	Excellent	Recherche binaire (moyenne)
O(n)	Temps linéaire	Le temps d'exécution est linéairement proportionnel à la taille des données d'entrée	Bien	Recherche de force brute
O(n + k)	Temps combiné / additif	Complexité combinée de deux entrées distinctes	Bien	Tri de comptage
O(n log n)	Temps quasilinéaire	À mesure que la taille des entrées augmente, le nombre de divisions nécessaires pour résoudre le problème augmente lentement en raison de la croissance logarithmique	Mauvais	Toi de fusion, tri tas
O(n^2)	Temps quadratique	Implique des itérations ou des comparaisons imbriquées pour chaque élément	Horrible	Tri de sélection
O(2^n)	Temps exponentiel	Implique une recherche ou un énumération exhaustif de toutes les combinaisons possibles de l'entrée, le temps d'exécution augmente de façon exponentielle	Horrible	TSP (programmation dynamique)
O(n!)	Temps factoriel	Implique une recherche ou un énumération exhaustif de toutes les combinaisons possibles de l'entrée, le temps d'exécution augmente factoriellement	Horrible	TSP (force brute)

Table de complexité de l'espace grand

Taper	Nom	Explication	Statut	Exemple
O(1)	Espace constant	L'algorithme nécessite une quantité fixe de mémoire supplémentaire, quelle que soit la taille d'entrée	Excellent	Trie de tas
O(log n)	Espace logarithmique	L'utilisation de l'espace augmente lentement par rapport à l'augmentation de la taille des données d'entrée	Excellent	Tri rapide
O(n)	Espace linéaire	L'utilisation de l'espace évolue linéairement avec la taille d'entrée	Bien	Fusion
O(n + k)	Espace combiné / additif	L'utilisation de l'espace évolue linéairement avec la somme de n et k	Mauvais	Radix Toi

Définitions

Terme	Définition	Exemples
Type de données abstrait (ADT)	Représente une description de haut niveau d'un type de données, en se concentrant sur son comportement et ses opérations plutôt que sur les détails de mise en œuvre spécifiques	pile, file d'attente, dictionnaire, séquence, set
Structure de données	Technique ou stratégie pour mettre en œuvre un type de données particulier, l'organisation et le stockage des données de manière spécifique pour faciliter les opérations efficaces	Array, liste liée, table de hachage, arbres (arbre de recherche binaire, tas, arbres rouges / noirs

Cours de collections Java

• Collection
  • Ensemble
    • Hashset
    • LinkedHashset
      • Triage
      • Navigableset
        • Arbre
  • Liste
    • Arraylist
    • Listin lié
    • Vecteur
      • Empiler
  • File d'attente
    • File d'attente prioritaire
      • Se débarrasser
        • Arrayequeue
• Carte
  • Hachage
  • Hashmap
  • LinkedHashmap
    • Trié
    • Navigablemap
      • Tramper

Comparaison des types de collecte:

Taper	Éléments en double	Ordre des éléments	Doit ajouter / supprimer dans un ordre spécifique
Liste	Autorisé	Par index	Non
Carte	Autorisé pour les valeurs	Java utilise le HashCode () de la clé pour déterminer l'ordre, pour nous, il n'est pas trié	Non
File d'attente	Autorisé	Récupéré dans l'ordre défini	Oui
Ensemble	Interdit	Seulement dans l'arbre	Oui

Attributs de collecte:

Taper	Interface	Trié?	Appelle hashCode() ?	Appelle compareTo() ?
Arraylist	Liste	Non	Non	Non
Listin lié	Liste, Deque	Non	Non	Non
Arrayeque	File d'attente, Deque	Non	Non	Non
Hashset	Ensemble	Non	Oui	Non
Arbre	Définir, triage	Oui	Non	Oui
LinkedHashset	Ensemble	Non	Oui	Non
Hashmap	Carte	Non	Oui	Non
LinkedHashmap	Carte	Non	Oui	Non
Tramper	Carte, triée	Oui	Non	Oui

Les structures de données qui impliquent le tri ne permettent pas les valeurs nulles.