eGospodarka.pl

eGospodarka.plGrupypl.comp.programming › Quciksort a najmniejsza liczba odpytywań
Ilość wypowiedzi w tym wątku: 5

  • 1. Data: 2019-11-24 09:49:52
    Temat: Quciksort a najmniejsza liczba odpytywań
    Od: Borneq <b...@a...hidden.p>

    Pytanie z Algorytmów i struktur danych
    Co się zdarzy, gdy funkcja oceniająca będzie dawała dziwne wyniki:
    typu A<B , B<C, ale C<A ?
    Czy w QuickSort zawsze pyta się minimalna ilość razy?
    Ale z drugiej strony, może być początkowe posortowanie takie że
    QuickSort będzie miał złożoność kwadratową, czyli na pewno nie pyta
    minimalna ilość razy. Co wtedy? QuickSort się wykrzaczy? Jak się to objawi?


  • 2. Data: 2019-11-24 16:42:33
    Temat: Quciksort a najmniejsza liczba odpytywań
    Od: g...@g...com

    Dla prostoty weźmy Haskellową implementację (pseudo) quicksorta:

    qsort [] = []
    qsort (h:t) = (qsort [x|x<-t, x<h]) \
    ++[h]++(qsort [x|x<-t, x>=h])

    Jeżeli tylko
    x >= y <=> ~(x < y)
    i jeżeli każde wywołanie x < y daje tę samą wartość, to lewa i prawa strona listy
    będzie każdorazowo malała przy kolejnych wywołaniach rekurencyjnych (bo są rozłączne,
    i wyciągamy z listy jeden element, h).
    Dlatego brak przechodniości operatora < nie powinna mieć wpływu na to, czy algorytm
    się zakończy.

    W prawdziwym quicksorcie jest lepiej, bo tam wywołujesz funkcję porównującą tylko raz
    na iterację dla każdego elementu, i przerzucasz elementy na lewo i prawo od pivota.
    Ale schemat rekursji jest dokładnie taki sam.

    Rezultat będzie oczywiście niezdefiniowany, ale algorytm się zakończy.


  • 3. Data: 2019-11-24 21:50:33
    Temat: Re: Quciksort a najmniejsza liczba odpytywań
    Od: Tomasz Konstanty Maluszycki <d...@g...com>

    On Sunday, November 24, 2019 at 8:49:55 AM UTC, Borneq wrote:
    > Pytanie z Algorytmów i struktur danych
    > Co się zdarzy, gdy funkcja oceniająca będzie dawała dziwne wyniki:
    > typu A<B , B<C, ale C<A ?
    > Czy w QuickSort zawsze pyta się minimalna ilość razy?
    > Ale z drugiej strony, może być początkowe posortowanie takie że
    > QuickSort będzie miał złożoność kwadratową, czyli na pewno nie pyta
    > minimalna ilość razy. Co wtedy? QuickSort się wykrzaczy? Jak się to objawi?

    Objawi ci się to kwadratową złożonością algorytmu...
    czyli dla tablicy 1000 elementów wykonasz milion porównań.
    Mała ciekawostka: największym koszmarem quicksorta jest tablica częściowo
    posortowana.


  • 4. Data: 2019-11-25 05:51:57
    Temat: Re: Quciksort a najmniejsza liczba odpytywań
    Od: "M.M." <m...@g...com>

    On Sunday, November 24, 2019 at 9:50:35 PM UTC+1, Tomasz Konstanty Maluszycki wrote:
    > On Sunday, November 24, 2019 at 8:49:55 AM UTC, Borneq wrote:
    > > Pytanie z Algorytmów i struktur danych
    > > Co się zdarzy, gdy funkcja oceniająca będzie dawała dziwne wyniki:
    > > typu A<B , B<C, ale C<A ?
    > > Czy w QuickSort zawsze pyta się minimalna ilość razy?
    > > Ale z drugiej strony, może być początkowe posortowanie takie że
    > > QuickSort będzie miał złożoność kwadratową, czyli na pewno nie pyta
    > > minimalna ilość razy. Co wtedy? QuickSort się wykrzaczy? Jak się to objawi?
    >
    > [...]
    > Mała ciekawostka: największym koszmarem quicksorta jest tablica częściowo
    > posortowana.

    Trzeba wybierać losowo element 'podziału'.
    Pozdrawiam


  • 5. Data: 2019-11-25 16:23:17
    Temat: Re: Quciksort a najmniejsza liczba odpytywań
    Od: Borneq <b...@a...hidden.pl>

    W dniu 24.11.2019 o 16:42, g...@g...com pisze:
    > Dlatego brak przechodniości operatora < nie powinna mieć wpływu na to, czy algorytm
    się zakończy.

    A czy da się uzyskać infrmację, że w pewnym kroku porównanie było
    nieprzechodnie?
    A co gdy mamy wiele elementów równych sobie, tak że mamy zawsze wybór z
    trzech a nie dwóch możliwości, gdyby były tak samo prawdopodobne, to
    zysk byłby log(3)/log(2)=1.58 raza.

strony : [ 1 ]



Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: