Formulaire

Complexités essentielles

Opération / pattern	Coût typique
accès tableau par indice	$\Theta(1)$
parcours de $n$ éléments	$\Theta(n)$
deux boucles imbriquées sur $n$	$\Theta(n^2)$
recherche dichotomique	$\Theta(\log n)$
tri efficace classique	$\Theta(n\log n)$
redimensionnement ponctuel d’un tableau dynamique	$\Theta(n)$
insertion amortie dans un tableau dynamique	$\Theta(1)$

$$O = \text{borne sup.}, \qquad \Omega = \text{borne inf.}, \qquad \Theta = \text{ordre exact}$$

Doubling ratio

Si $T(n) \sim an^b$ :

$$\frac{T(2n)}{T(n)} \to 2^b$$

• ratio $\approx 2$ → linéaire
• ratio $\approx 4$ → quadratique
• ratio $\approx 8$ → cubique

---

Stack, Queue et LinkedList

Stack — LIFO

push(x)   ajoute au top
pop()     retire le top
peek()    lit le top
isEmpty()

Avec une singly linked list : top en tête → push / pop en $\Theta(1)$.

node.next = first;
first = node;

Queue — FIFO

Queue<Integer> q = new ArrayDeque<>();

q.add(x);      // enqueue
q.remove();    // dequeue
q.peek();      // lire la tête

LinkedList : parcours

À privilégier :

for (E x : list) {
    process(x);
}

ou :

Iterator<E> it = list.iterator();

while (it.hasNext()) {
    E x = it.next();
}

À éviter :

for (int i = 0; i < list.size(); i++) {
    process(list.get(i));
}

Sur une LinkedList, ce dernier pattern peut coûter $\Theta(n^2)$.

---

Patterns Java à retrouver vite

Référence vs valeur

int[] a = {1, 2, 3};
int[] b = a;

b[0] = 99;
// a[0] vaut aussi 99

Java passe toujours les arguments par valeur ; pour un objet, la valeur copiée est sa référence.

Itérateur fail-fast

Pattern classique :

private final long expectedOps = nOp;

public E next() {
    if (expectedOps != nOp) {
        throw new ConcurrentModificationException();
    }

    // avancer
}

Test rapide d’une structure

assertTrue(stack.empty());

stack.push(1);
assertEquals(1, stack.peek());
assertEquals(1, stack.pop());

assertThrows(EmptyStackException.class, stack::pop);

---

Pièges centraux

Overflow

Éviter :

int mid = (lo + hi) / 2;

Préférer :

int mid = lo + (hi - lo) / 2;

Division entière

System.out.println(-1 / 2); // 0

Java tronque vers zéro.

Tableau dynamique

if (size == a.length) {
    a = Arrays.copyOf(a, 2 * a.length);
}

a[size++] = item;

Le redimensionnement coûte $\Theta(n)$, mais l’insertion reste $\Theta(1)$ amortie.

---

Mémoire JVM

stack mémoire → appels, paramètres, variables locales
heap          → objets et tableaux

-Xms → taille initiale du heap
-Xmx → taille maximale du heap

Le garbage collector récupère les objets devenus inaccessibles.

---

Algorithmes à compléter au fil du cours

Cette section sert uniquement à garder les squelettes centraux qu’il faut pouvoir retrouver rapidement.

Binary search

int lo = 0;
int hi = a.length - 1;

while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;

    if (a[mid] < key) {
        lo = mid + 1;
    } else if (a[mid] > key) {
        hi = mid - 1;
    } else {
        return mid;
    }
}

return -1;

À ajouter quand le cours y arrive : sorting, BST, heap, hashing, BFS/DFS, graphes, strings.