[Algorytmy] Ciągi k-uporządkowane

matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

[Algorytmy] Ciągi k-uporządkowane

Post autor: matinf »

Witam,
Mamy ciągi \(\displaystyle{ n}\) elementowe, tże \(\displaystyle{ A\le A[i+k]\le A[i+2k] \le...}\) - czyli k-uporządkowane.
Udowodnić, że każdy algorytm sortujący przez porównania wymaga pesymistycznie \(\displaystyle{ \Omega (n\log(k))}\) porównań.

Czyli mam pokazać ograniczenie dolne. To jakbym się do tego zabierał to policzyć ilość możliwych permutacji ciągu danego na wejściu, a potem pokazać jaka musi być minimalna wysokość drzewa, żeby rozpiąć tyle lisci.

Ok ? Jak mogę zliczyć takie ciągi ?-- 19 lis 2014, o 14:05 --Ok,
przyszło mi do głowy coś, co może pomóc oszacować liczbę możliwych wyników:

Będę wybierał pozycje dla każdego k-podciagu:

\(\displaystyle{ {n\choose k}\cdot {n-k\choose k}\cdot {n-2k\choose k}\cdot\dots\cdot{n-\left\lfloor \frac{n}{k} \right\rfloor
k\choose k}}\)

\(\displaystyle{ \ge \frac{n!}{k!^{\frac{n}{k}}} \approx (\frac{n}{k})^n}\)
A to niemożliwe, bo gdy \(\displaystyle{ k=1}\), to dostaniemy, że wysokość drzewa to \(\displaystyle{ n\log(n)}\)
Czyli wyszło jakby na odwrót - gdy mamy małe \(\displaystyle{ k}\) to ciąg jest prawie uporządkowany. Gdzie robię błąd ?
Ostatnio zmieniony 19 lis 2014, o 11:23 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
ODPOWIEDZ