data structures and algorithms in swift

structures de données et algorithmes dans le swift

Ce sont le résumé de mes apprentissages à partir d'un cours Udemy: "Structures de données et algo dans Swift"

Complexité du temps:

1. Temps constant
2. Temps linéaire
3. Temps quadratique
4. Temps logarithmique - recherche binaire
5. Temps quasilinéaire

Nœud:

• Racine
• Enfant -> Enfant gauche et enfant droit
• Feuille

Liste liée

• Les éléments sont connectés les uns aux autres par référence appelée nœuds

• Le 1er nœud de la liste liée est appelé tête

• Le dernier nœud est appelé nœud de queue

  Opérations: - Push - APPEND - INSERT - POP - Removelast - Supprimer

Pile (lifo)

• Pousser
• Populaire

File d'attente (FIFO)

• Jeter un coup d'œil
• Enquérir
• Déshabiller

Récursivité

• Cas de base - qui arrête la récursivité.
• Cas récursif

Arbres:

• Profondeur Première traversée
• Traversé de commande
• Recherche
• Arbre binaire (peut avoir max de: 2 enfants seulement - à gauche et à droite)
  • Dans la traversée -> Leftchild -> Node -> RightChild
  • Traversion post-commande -> LeftChild -> RightChild -> Node
  • Traversion de pré-commande -> Node -> LeftChild -> RightChild
• Arbre de recherche binaire

Recherche linéaire

• Sur)

Recherche binaire

• Tableau trié
• Index moyen - gauche ou droite
• Meilleur moment: o (1)
• Pire moment: o (log n)

Tri bulle

• Non trié
• Meilleur moment: o (n) (si déjà trié)
• Pire temps: o (n ^ 2)

Tri de sélection

• Échangez l'élément minimum dans le tableau avec l'index actuel
• Passez à l'index suivant et répétez l'étape 1
• Meilleur temps: o (n ^ 2)
• Pire temps: o (n ^ 2)

Tri insertion

• Non trié
• Meilleur moment: o (n)
• Pire temps: o (n ^ 2)

Graphique:

Consister en

• Sommets / sommet
• Bords / bord

Types de graphiques:

• Graphiques pondérés
• Graphiques dirigés
• Graphiques non dirigés (bidirectionnel)

Liste d'adjacence

• Moyen le plus souvent / largement utilisé pour créer et représenter un graphique