Adam
Woźniak
software architect
and developer
Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)
WitamZ mojej strony ostatnia zagadka ;]
Zagadka:
Mamy tablice int'ów o rozmiarze n.
O elementach w tablicy wiemy tylko tyle, że w tablicy są zapisane po sobie dwa ciągi rosnących liczb, to znaczy:
fragment od indeksu 1 do j jest posortowany
fragment od indeksu j+1 do n jest posortowany
... gdzie j jest jakimś indeksem z przedziału (1, n).
Celem zagadki jest znalezienie algorytmu, który scali te dwa ciągi, działającego w czasie O(n) i potrzebującego jedynie O(1) dodatkowej pamięci.
Czyli wynikiem działania algorytmu, ma być tablica z już posortowanymi elementami.
--------------------------------
Od razu mówię, że sam rozwiązania nie znalazłem. Kiedyś, po latach, przypomniała mi się ta zagadka i dość szybko wygooglałem odpowiedni algorytm. Znaleziony przeze mnie (w internecie) algorytm okazał się nietrywialny ;]
A o zagadce tej postanowiłem napisać, bo zagadka, z pozoru, wydaje się krótka i prosta, a jak się okazało, wcale taką nie jest :)
Poza tym, w ekstremalnych zastosowaniach, warto mieć świadomość, że takiego scalenia jesteśmy w stanie dokonać *bez* dodatkowej pamięci (tablicy) o tym samym rozmiarze.
Pozdrawiam, Adam Woźniak
PS. Jeśli ktoś ciekaw jest rozwiązania, to za kilka dni dam adresy do opisu algorytmu.Adam Woźniak edytował(a) ten post dnia 20.05.10 o godzinie 22:41