Mamy tablicę n liczb naturalnych. Zaproponuj możliwie szybki algorytm, który obliczy, ile zamian
liczb dokonałby na tym ciągu algorytm sortowania bąbelkowego (porządek niemalejący).
Chodzi mi o to aby algorytm miał jak najmniejszą złożoność.
Macie jakieś podpowiedzi?
Słyszałem coś że trzeba policzyć ilość inwersji, ale to nadal "pętla w pętli".
Chyba można to wyliczyć na podstawie analizy samej metody.
- małe klucze z końca tablicy są tu przenoszone na początek w jednym przejściu, co daje k=i-j przestawień;
gdzie: i, j - pozycje elementu, początkowa i finalna
- natomiast te wielkie klucze, z początku tablicy są przesuwane tylko o 1 w każdym przejściu, co i tak w sumie daje to samo: j-i.
Zatem algorytm który to wyliczy dokładnie miałby pewnie złożoność liniową, może 2n - jak w przypadku szukania mediany.