sortuj na tablicach w czasie O (n + mlogm) - algorytm, struktury danych, informatyka

Robiłem rzeczy algorytmiczne. Istnieją dwie tablice, tablica A o długości n została posortowana w porządku rosnącym, natomiast tablica B o długości m nie jest. Pytanie prosi nas o stworzenie tablicy, w której liczby całkowite m + n są sortowane w porządku rosnącym. I powinno się kończyć w czasie o (n + mlogm). To, co myślę, to najpierw wykonać sortowanie korespondencji seryjnej na B i może zająć czas o (mlogm). Następnie wykonaj sortowanie korespondencji seryjnej na A i B, ale wyraźnie zajmuje to więcej czasu. Czy są jakieś inne rozwiązania?

Odpowiedzi:

Masz rację, że pierwszym krokiem jest sortowanie drugiej tablicy w O (mlogm).

Ale drugim krokiem jest proste scalenie posortowanych tablic, które wymagają O (n + m)

(scalanie jest równe fazie scalania połączenia. Dowolny przykład)

Tak więc ogólna złożoność to O (mlogm + m + n) = O (mlogm + n)