Algorithmique avancée et structures de données

La notation $O(n^2)$ signifie que le temps d'exécution croît proportionnellement au carré de la taille des données. Si vous doublez la taille de l'entrée, le temps est multiplié par 4. C'est typique des algorithmes de tri simples comme le tri à bulles.

💡 À retenir : $O(n^2)$ est souvent inefficace pour de très grands volumes de données.

1. Chouf ch7al mn mara kat-t-executa l-boucle.
2. Ila kanet boucle wa7da kat-mchi mn 1 l-n, l-complexité hiya $O(n)$.
3. Ila kanet boucle dakhla f boucle (imbriquée), kaddir $n \times n$ ya3ni $O(n^2)$.

💡 À retenir : Dima 7seb l-3adad dyal l-i3adat (itérations) dyal l-code li dakhli.

1. La Pile suit le principe LIFO (Last In, First Out) : le dernier élément ajouté est le premier sorti.
2. La File suit le principe FIFO (First In, First Out) : le premier élément ajouté est le premier sorti.

💡 À retenir : Pile = empiler/dépiler ; File = enfiler/défiler.

L-récursivité kat-kheli l-code ykon sghir w m9ad (élégant) f l-machakil li fiha t-takaror (ex: factorielle, parcours d'arbres). Kat-kheli l-mouchkil l-kbir ywali machakil sghar.

💡 À retenir : Dima khass tkon "condition d'arrêt" bach mayt-bloquach l-programme.

Ils permettent de stocker des données de manière ordonnée. La recherche, l'insertion et la suppression se font en $O(\log n)$ en moyenne, ce qui est beaucoup plus rapide qu'un tableau non trié ($O(n)$).

💡 À retenir : L'efficacité dépend de l'équilibre de l'arbre.

1. Créer un nouveau nœud.
2. Pointer le next du nouveau nœud vers le nœud suivant actuel.
3. Mettre à jour le pointeur du nœud précédent pour qu'il pointe vers le nouveau.

💡 À retenir : Ne jamais perdre le pointeur next avant d'avoir lié le nouveau nœud.

1. 7awel t-evita l-boucles li dakhlin f b3diyat-hom (imbriquées) ila kan momkin.
2. St3mel structures dyal l-ma3loumat li mnasba (ex: Hash Map bdl tableau).
3. 7yed l-i3adat li ma-3ndhomch l-fayda.

💡 À retenir : L'optimisation doit se faire sur les parties du code les plus utilisées.

C'est une variable qui ne contient pas une valeur directe, mais l'adresse mémoire d'une autre variable. Cela permet de manipuler des données dynamiquement sans les copier.

💡 À retenir : Un pointeur pointe vers une "case" mémoire précise.

Non, elle nécessite impérativement un tableau trié pour pouvoir comparer la valeur cherchée avec l'élément central et décider de la moitié à éliminer.

💡 À retenir : Tri obligatoire avant dichotomie.

L'accès est en $O(1)$ car on calcule l'adresse mémoire directement via l'index : adresse = base + index * taille_element.

💡 À retenir : Le tableau est la structure la plus rapide pour l'accès direct.

Chaque appel récursif ajoute une couche à la pile d'appels (stack) en mémoire. Si la profondeur est trop grande, la pile sature et le programme plante.

💡 À retenir : La récursivité profonde est risquée pour la mémoire.

C'est un arbre où tous les niveaux sont remplis, sauf éventuellement le dernier qui est rempli de gauche à droite.

💡 À retenir : Cette structure est idéale pour implémenter des tas (heaps).