Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-05-13 14:43:38.
Revizia anterioară   Revizia următoare  

Costperm

Solutie O(N*log N)

Fie sirul A, permutarea data.
Fiecare element A[k] va fi implicat intr-un numar Y de interschimbari, unde Y = numarul de elemente A[l], cu A[l]>A[k] si l<k. Evident costul unei interschimbari de acest gen va fi A[k]. Astfel, vom parcurge sirul A, pentru fiecare element A[k] vom afla Y si vom adauga la raspuns A[k]*Y.