Calculer le nombre d'inversions avec des techniques de discrétisation
L'objectif est de compter le nombre d'inversions dans une séquence d'entiers. Une inversion est une paire d'indices (i, j) telle que i < j et arr[i] > arr[j]. Nous allons explorer deux approches principales, toutes deux offrant une complexité temporelle de O(log n) après prétraitement.
Approche par Division et Fusion (Merge Sort)
Cette mé ...
Publié le 10 juin à 01h29