Soit {t} un tableau de taille {n,} et soit {\left\{i,j\right\}} une paire d’indices distincts dans {[\![ 0,n-1]\!] .}
On dit que la paire {\left\{i,j\right\}} représente une inversion (dans le tableau {t)} si on a {i\lt j} et {t_{i}>t_{j}.}
Un moyen na ̈if de compter les inversions d’un tableau est de tester toutes les paires {\left\{i,j\right\}.}
L’algorithme obtenu est alors de complexité {n^{2}.}
|
1 2 3 4 5 6 7 8 9 |
let nbinv_naif t = let n = Array.length t and inv = ref 0 in for i = 0 to n-2 do for j = i+1 to n-1 do if t.(j) < t.(i) then incr inv done; done; !inv;; val nbinv_naif : 'a array -> int = <fun> |
La fonction nbinv_naif ci-dessous apporte une solution.
Voici un exemple d’utilisation :
|
1 2 3 4 5 6 |
nbinv_naif [|9;1;11;4;8;3;13;7;5;12;2;6;10|];; - : int = 37 nbinv_naif [|9;1;11;4;8;3|];; - : int = 9 nbinv_naif [|13;7;5;12;2;6;10|];; - : int = 13 |
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres