Ponieważ nie ma działu "Algorytmy", a programik będę pisał w C to zamieszczam post tutaj:
Zadanie jest następujące:
mamy tablice n x m intow posortowaną wierszami i kolumnami. Chcemy znaleźć w niej liczbę x w czasie - uwaga O(n+m). Zna ktoś algorytm (pseudokod) jak to zrobić?
Dziękuję za pomoc
złożoność n+m.. hmm.. a nie wystarczy po prostu jechac forem po wierszach tak dlugo az trafisz na liczbe wieksza od Twojej i pozniej jechac po kolumnach dokladnie tak samo przeszukujac 2 pola jednoczesnie (bo nie wiesz dokladnie w ktorej kolumnie bedzie szukany element)?
szybciej to mozna zrobic dzielac tablice na 4 mniej wiecej w polowie. bierzesz dowolny elelemnet mniej wiecej na srodku i od razu bedzsz wiedzial w ktorej polowie sie on znajduje
Ja rozumiem że to posortowanie wygląda tak:
1 3 7
2 4 8
4 7 9
Wtedy tak jak napisał @krwq lecisz po pierwszym wierszu aż trafisz na liczbę >= x a potem przeglądasz sobie tą kolumnę gdzie się zatrzymałeś i poprzednią. To nam daje O(n+2m) co dla odpowiednio dużych n i m daje nam O(n+m)
Można by też to zrobić w czasie O(logn + logm) gdyby szukać połówkowo ;)
Ok, już rozumiem - wydaje się że to ma ręce i nogi :-)
Bardzo dziękuję za pomoc i pozdrawiam!
Cofam to co napisałem. Musisz ort! wszystkie poprzednie, a to nam daje inną złozonośc. Chyba ze liczby będą unikalne w tablicy ;]
Można też sprawdzic czy zadziała taki sposób: lecimy po krawędzi tablicy i szukamy liczby >= x a następnie lecimy po przekątnej tablicy i na przekątnej będzie szukana liczba.