Dominator - złożoność obliczeniowa

Witajcie,

Przed chwilą pisałem test kwalifikacyjny na praktyki. Zadaniem było wyznaczenie dominatora w wektorze. Zwracana wartość to jakikolwiek indeks wektora z dominatorem, a jeżeli go nie ma to -1. Dominator to wartość która występuje w więcej niż połowie elementów

I teraz. Użyłem do tego dwóch zagnieżdżonych pętli for

1. O(n/2)
2. O(n) ?? nie wiem jak zapisać tą złożoność
   pierwsza ustawia indeks tablicy x, a druga od x sprawdza ile razy występuje określona wartość.

W treści zadania było napisane że ma być max(O(n)).
Da się to zrobić w O(n) żeby było w miarę prosto, nie tworząc tablicy struktur? BTW zajętość pamięci ma być O(1).

To co napisałeś to najgorsze sensowne rozwiązanie i ma złożoność O(n^2). Ale jeśli nie umiesz tego nawet policzyć to nie dziwota że nie wymyśliłeś szybszego rozwiązania...
Masz tam przecież:
n+ (n-1) + (n-2) + ... + 1 = n*(n-1)/2 bo to suma ciągu arytmetycznego i to nam daje O(n^2)
Twój "dominator" to jest mediana, ale rozumiem że statystyki nigdy się nie uczyłeś? ;]
Jeśli dominator istnieje to jest medianą zbioru, więc trzeba najpierw znaleźć medianę.
A rozwiązaniem tego problemu jest algorytm magicznych piątek.
http://pl.wikipedia.org/wiki/Algorytm_magicznych_piątek

edytowane żeby nikogo nie wprowadzać w błąd

Jak to mediana? 1, 2, 3, 4, 5 ma medianę 3, ale 3 nie spełnia definicji dominatora.

Shalom a ty przeczytales co to wg jego definicji dominator? ;p

Napisal ze dominatorem bedzie ta wartosc ktora wystepuje najwiecej razy w danym zbiorze liczb. Jesli wszystkie po tyle samo to nie ma dominatora i zwraca -1. Mediana to jest wartosc przecietna danego zbioru lub kwantyl rzedu 1/2 dla danych losowych.

Co do tematu to 1 petla for to zlozonosc O(n) 2 zagniezdzone to juz O(n^2) niestety.

Nie wiemy czy na wejsciu twoja tablica byla posortowana jesli tak to przykladowo zeby uzyskac zlozonosc O(n) mozna. Przejrzec raz tablice przy tym ze zapamietujemy kazdy elemtn w zmiennej i dopoki nastepny jest taki sam jak poprzedni to inkrementujemy jakis tam licznik. Mozemy potem te zliczenia wystapien wrzucic do jakiejs tablicy i wartoscia maksymalna bedzie odpowiedni index tablicy(trzeba sobie przeliczyc).

Wtedy kazda tablice przegladasz 1 raz i 1 petla. Dobrze mysle? ;p

@Krycho

Sorta nie było, właśnie nie chciałem jakiegoś topornego rozwiązania z dodatkowymi tablicami tworzyć.

Edit:

Nie dominanta tylko dominator. Test był w angielskim i tam tak go nazwano, nie wiem czy jest polski odpowiednik tego.

Ech człowiek zrobi skrót myślowy i od razu znajdzie się kilku mądrych. Skojarzenie z medianą było jak najbardziej poprawne bo mając medianę możemy spokojnie rozwiązać podany problem za pomocą jednego przeglądnięcia tablicy. A że szukanie mediany też jest liniowe to wszystko jest ok. Jedyne poprawne rozwiązanie tego zadania to:

• magiczne piątki do szukania mediany
• liniowe zliczenie ile razy ta mediana wystąpiła w wejściowym ciągu

Sortowanie odpada bo nie posortujesz w miejscu w O(n). W ogóle sortowanie w O(n) możesz zrobić tylko przy pewnych ograniczeniach na zakres liczb i przy użyciu dużej ilości pamięci.

 
template <class RandIt>
bool haveDenominator(RandIt first, RandIt last){
        RandIt middle=(last-first)/2+first;
        nth_element(first,last,middle);
        return middle-first<count(first,last,*middle);
}

KISS.

Cofam to co mówiłem - można ten problem rozwiązać jeszcze prościej. Wystarczy zrobić tak:

• bierzemy pierwszy element z tablicy i robimy licznik = 1
• przeglądamy tablicę od początku i jeśli trafiamy na ten sam element który mamy zapamiętany jako "kandydata" to podbijamy licznik, a jeśli na inny to zmniejszamy
• jeśli licznik miałby spaść poniżej 0 to zmieniamy kandydata i ustawiamy licznik = 1
  Na końcu robimy drugi przebieg żeby sprawdzić czy znaleziony kandydat wystąpił więcej niż n/2 razy.
  Łatwo zaobserwować że jeśli element istnieje to podany wyżej algorytm musi go znaleźć.

no tak, ale możesz odrzucić pierwszych n/2 kandydatów zanim znajdziesz właściwą wartość, a i tak dla każdego kandydata musisz swoim algorytmem sprawdzić co najmniej n/2 tablicy, więc masz złożoność o(n*n).
Przykład:
1 2 3 4 4 4

Że co? Czy ja napisałem coś niewyraźnie? Dla twojego przykładu algorytm działa tak:
kandydat | krotność | który element wejściowego ciągu przeglądamy
1 1 1
1 0 2
3 1 3
3 0 4
4 1 5
4 2 6
W efekcie uzyskaliśmy informacje że kandydatem jest liczba 4. Robimy przebieg przez tablicę licząc 4 i wiemy już że 4 nie spełnia wymagania, bo występuje tylko n/2 razy.
Algorytm działa dlatego że skoro dominatorów jest przynajmniej n/2 +1 (tzn jest jeden, ale występuje tyle razy w ciągu) to postępując w ten sposób musimy na końcu uzyskać kandydata który jest dominatorem, o ile ten istnieje.

Mam wrażenie, że dominator jest najwyżej jeden.

@MarekR22 nie wiem jak można to łatwiej wyjaśnić. Tak jak napisał @bogdans dominator może być co najwyżej 1!
Dla twojego nowego przykładu 1 2 3 4 1 1:
kandydat | krotność | który element wejściowego ciągu przeglądamy
1 1 1
1 0 2
3 1 3
3 0 4
1 1 5
1 2 6
W efekcie kandydatem jest liczba 1. Przeglądamy znów całą tablicę i wychodzi nam że 1 nie jest dominatorem.

Spróbuje to wyjaśnić jeszcze prościej:

• skoro dominator występuje przynajmniej n/2+1 razy w ciągu to znaczy że tyle razy jego licznik zostanie podbity, lub obniżony zostanie licznik innego elementu.
• innych elementów jest nie więcej niż n/2 -1 więc ich liczniki mogą być podbite o nie więcej niż właśnie n/2 -1 (ew mogą obniżyć licznik innego elementu o nie więcej niż tyle)
  Widać wyraźnie że licznik dominatora, o ile ten istnieje, musi po przejściu całej tablicy być jedynym licznikiem który jest dodatni.

edit: jak widać nic w przyrodzie nie ginie -> podany problem jest problemem znanym
http://main.edu.pl/en/user.phtml?op=lesson&n=36&page=algorytmika

Miło, że się na mnie powołujesz, ale sam napisałeś takie coś:

skoro dominatorów jest przynajmniej n/2 +1
Jest to raczej niezgodne z tym, że denominator jest najwyżej jeden.