{2, 3}-SUM
3-SUM est la base de bien d'autres problèmes. On en reparlera bien plus tard, mais ce problème est une des bases algorithmique de la géométrie algébrique. Commençons par un problème simple, 2-SUM
2-SUM
Problème
- nom : 2-SUM
- données : Un tableau T d'entiers relatifs
- question : Existe-t-il deux indices $i$ et $j$ (ils peuvent être égaux) tels que $T[i] + T[j] = 0$ ?
Donnez une solution au problème 2-SUM avec comme complexité :
- temporelle de $\mathcal{O}(T.\mbox{\small longueur}^2)$
- spatiale en $\mathcal{O}(1)$
Donnez une solution au problème 2-SUM avec comme complexité :
- temporelle de $\mathcal{O}(T.\mbox{\small longueur}\ln(T.\mbox{\small longueur}))$
- spatiale en $\mathcal{O}(T.\mbox{\small longueur})$
Un nouvel algorithme :
Donnez une solution au problème 2-SUM avec comme complexité $\mathcal{O}(\max(T))$.
Est-ce réaliste ?
3-SUM
Problème
- nom : 3-SUM
- données : Un tableau T d'entiers relatifs
- question : Existe-t-il trois indices $i$, $j$ et $k$ (ils peuvent être égaux) tel que $T[i] + T[j] + T[k] = 0$ ?
Donnez une solution au problème 3-SUM avec comme complexité :
- temporelle de $\mathcal{O}(T.\mbox{\small longueur}^3)$
- spatiale en $\mathcal{O}(1)$
Enfin, l'exercice dur qui montre que l'on peu résoudre 3-SUM plus efficacement avec un coût en mémoire :
Donnez une solution au problème 3-SUM avec comme complexité :
- temporelle de $\mathcal{O}(T.\mbox{\small longueur}^2)$
- spatiale en $\mathcal{O}(T.\mbox{\small longueur})$