mergesort

Odpowiedz Nowy wątek
2019-06-20 22:07
0

Mam takie zdanie z książki

Top-down mergesort uses between ½ N lg N and N lg N compares to
sort any array of length N.

I nie bardzo kumam o co chodzi.

    for (int k = lo; k <= hi; k++) {
    int i = lo, j = mid+1;
        if      (i > mid)              a[k] = aux[j++];
        else if (j > hi)               a[k] = aux[i++];
        else if (less(aux[j], aux[i])) a[k] = aux[j++];
        else                           a[k] = aux[i++];

O jakie compares chodzi ? O less ? Czy ogólnie i > mid itp. Przepraszam że zadaje głupie pytania.

Nie wiem, czy głupie, też nie rozumiem tego zadania. W ogóle nie widzę tam polecenia, raczej stwierdzenie, a tej drugiej części od "compares" nie rozumiem. - Silv 2019-06-20 22:31
To twierdzenie o algorytmie mergesort. Mówi ono że ,że algorytm zawsze musi wykonać ileś tam jakiś porównań. Jeżeli studiowałeś informatykę powinno to być Ci znane. Wkleiłem tylko fragment w którym są robione jakieś porównania. - szrot 2019-06-20 22:34
A, "compares" to rzeczownik... widać rzadko widzę to pojęcie w tej formie. I przeczytałem "zadanie", a nie "zdanie". - Silv 2019-06-20 22:36

Pozostało 580 znaków

2019-06-21 09:57
0

Mergesort wykonuje miedzy 1/2nlogn a nlogn porownan miedzy elementami tablicy. Czyli jest big teta od n. Otworz CLRS albo Zajrzyj tutaj: https://algs4.cs.princeton.edu/22mergesort/


edytowany 1x, ostatnio: lion137, 2019-06-21 09:58

Pozostało 580 znaków

2019-06-21 10:26
0

Czyli chodzi o less(aux[j], aux[i])) . Liczyłem te operacje na kodzie. Liczba porównań dla less wynosi co maksymalnie 1/2nlgn. Liczba porównań dla wszystkich operacji jak if (i > mid) itd wynosi zawsze nlgn.
Nadal nie czaję. Mam przy okazji takie pytanie. Czy aby posługiwać się algorytmami to trzeba znać te wszystkie dowody przez indukcje itp.

Introduction to Algorithms to ciężkostrawna książka. Wybrałem Algorithms Sedgewicka.

edytowany 9x, ostatnio: szrot, 2019-06-21 11:00

Pozostało 580 znaków

2019-06-21 11:23
0

To Wez tego Sedgwick'a to Ci sie rozjasni. Wypadaloby znac dowody, to pozwala zrozumiec algorytm.


Pozostało 580 znaków

2019-06-21 11:37
0

Skopałem kod. I źle liczy. Teraz jest ok.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0