Jaka jest srednia, a jaka maksymalna ilosc inwersji dla tablicy o rozmiarze n? Zakladamy, ze tablica jest roznowartosciowa i wszystkie permutacje sa jednakowo pradopodobne.
nie chodzi mi o gotowa odp, bardziej o sposob jak to liczyc
z gory dzieki
0
0
Maksymalna ilość inwersji to po prostu odwrotne posortowanie czyli:
dla pierwszej liczby inwersji jest n-1 (wszystkie liczby oprócz niej samej)
dla drugiej liczby n-2 (wszystkie oprócz niej samej i liczby pierwszej)
itd
dla n-1 liczby mamy 1 inwersję
dla n-tej liczby mamy 0 inwersji
to jest ciąg arytmetyczny, sumujemy i wychodzi.
0
ok, dzieki
a ma ktos pomysl na srednia ilosc inwersji?
0
Załóżmy (chyba bez straty ogólności) że elementy w tablicy to liczby od 1 do n. Tablicę permutacji P transformujemy na tablicę inwersji I, gdzie I[k] to ilość elementów większych od P[k] spośród elementów P[1]...P[k - 1] (podobnie jak to robił Shalom). Element I[k] może przyjmować wartości z zakresu 0..(k - 1). Każda z tych wartości jest jednakowo prawdopodobna (dlaczego? to już kolejne pytanie :) musiałbym poszperać w notatkach). Dodatkowo każda taka tablica inwersji wyznacza inną tablicę permutacji (tzn zachodzi bijekcja). Wystarczy obliczyć wartość oczekiwaną sumy elementów tablicy I. Wynik wyjdzie taki jak w poście Shaloma podzielone przez 2.
0
dzieki, ale i tak nic z tego nie rozumiem :D
0
Sorry popełniłem jeden znaczący błąd. Poprawiłem go i pogrubiłem poprawkę.
Przykładowo mamy tablicę P:
5 4 1 6 3 2 7
Robimy z tego tablicę I:
0 1 2 0 3 4 0
Wiadomo, że element I[k] musi być mniejszy od k oraz że każda poprawna tablica inwersji wyznacza jednoznacznie tablicę permutacji. Ilość inwersji to suma po elementach z tablicy inwersji. Wartość oczekiwana elementu I[k] to (k - 1) * (k - 2) / 2 (ponieważ z jednakowym prawdopodobieństwem może przyjąć dowolną wartość z zakresu [0 .. k - 1]). Elementy są niezależne. Z liniowości wartości oczekiwanej można obliczyć wartość oczekiwaną sumy elementów tablicy I (czyli ilości inwersji). Wartość oczekiwana to wartość średnia.
0
ok, dzieki, wszystko jasne :)