@RR_Woda: Yy, bierzesz set, dodajesz all, robisz gety, jeśli nie ma to koniec. Coś mi chyba umyka bo to trochę too obvious, co w moim rozwiązaniu jest nie tak?
Będziemy iterować maksymalnie 32 razy po naszym zbiorze wejściowym, więc mamy liniową złożoność obliczeniową.
Możesz wyjaśnić? Mi wychodzi złożonośc liniowo-logarytmiczna. Część liniowa to iterowanie po każdym przedziale (długość proporcjonalna do długości inputu), część logarytmiczna to bisekcyjne skracanie przedziału (bo musimy wykonac log(N) iteracji)
EDIT: właściwie już sam zrozumiałem, że z typu danych (32 bity) wynika że będzie maksymalnie
@RR_Woda: to może ja też wrzuce swoje rozwiązanie(a właściwie modyfikacje do już istniejących)
I metoda - z sortowaniem Zamiast sortować całą tablicę zmodyfikowałbym algorytm qsort Wiki. Na stronie wiki jest gif, który pokazuje metode sortowania: dzielenie i sortowanie od najniższych zakresów. Gdyby w którymś z niższych zakresów brakowało liczby przerywam sortowanie i zwracam wynik
II metoda - z flagami Zamiast alokować pamięć na wszystkie możliwe liczby można zaalokować 16 razy
ć pamięć na wszystkie możliwe liczby można zaalokować 16 razy mniej flag niż liczb i sprawdzać początkowe 1/16 liczb. Jeśli tam nie ma brakującej liczby to sprawdzam kolejną 1/16 zakresu.
@RR_Woda: Co do moich algorytmów oczywiście w najgorszym przypadku wydajność jest taka jak w rozwiązaniach przedstawionych w blogu. Jednak w praktyce rzadko kiedy brakująca liczba jest pod koniec przedziału - i bazując na tym założeniu szukałbym oszczędności. Podobnie rzadko kiedy trafi się ogromna tablica dlatego unikałbym alokowania 0.5GB pamięci dla każdego rozwiązania
@Bisk: @RR_Woda: Skąd taka złożoność (czasowa)? Mam na myśli set jako coś co używa mapy/słownika (java), czyli to rozwiązanie to coś w stylu ustawiania flag na pozycjach, gdzie pozycje są hashami elementów (czyli elementami, bo to liczby).
Jeśli jako set korzystamy z std::set to jest on implementowany jako samobalansujace drzewo binarne wiec dodanie lub usunięcie elementu ma złożoność log(n) a elementów jest N wiec mamy N*log(N)
jeśli wykorzystamy std::unordered_set wówczas jest to faktycznie pewna nowa opcja nie opisana w poście. Włożenie i usuniecie ma złożoność O(1) ale złożoność pamięciowa jest M(N).
@RR_Woda: @Bisk: Tak, to prawdopodobnie odpowiednik unordered_set, na pewno nie ordered (TreeSet), wstawianie i usuwanie jest O(1) z wyjątkami jeśli mamy taki sam hash dla dwóch różnych elementów, ale na liczbach do pewnego zakresu to nie zajdzie.
http://goo.gl/iTrS8R
#programowanie, #cpp, #python, #rekrutacja
Ciekawy i fajny blog.
1) Nie musisz przez skracarkę wrzucać
2) wciąƶ bez js nie działa :(
@RR_Woda:
Możesz wyjaśnić? Mi wychodzi złożonośc liniowo-logarytmiczna. Część liniowa to iterowanie po każdym przedziale (długość proporcjonalna do długości inputu), część logarytmiczna to bisekcyjne skracanie przedziału (bo musimy wykonac log(N) iteracji)
EDIT: właściwie już sam zrozumiałem, że z typu danych (32 bity) wynika że będzie maksymalnie
I metoda - z sortowaniem
Zamiast sortować całą tablicę zmodyfikowałbym algorytm qsort Wiki.
Na stronie wiki jest gif, który pokazuje metode sortowania: dzielenie i sortowanie od najniższych zakresów. Gdyby w którymś z niższych zakresów brakowało liczby przerywam sortowanie i zwracam wynik
II metoda - z flagami
Zamiast alokować pamięć na wszystkie możliwe liczby można zaalokować 16 razy
JS jest w planie do zrobienia, bardzo fajnie ze to odkryłeś bo do głowy by mi nie przyszło sprawdzić
@Tail_Gunner:
AD 1. ciekawe... obliczeniowo mogło by poprawić ale w najgorszym przyadku nadal mamy O(n*log(n))
pamięciowo albo modyfikujemy albo robimy kopie
AD 2.
jak zablokujesz 16 razy mniej to masz -
pamięciowa stała równa 1/16 * 2^32
obliczeniowa 16 * n
@Porana123:
Jeśli jako set korzystamy z std::set to jest on implementowany jako samobalansujace drzewo binarne wiec dodanie lub usunięcie elementu ma złożoność log(n) a elementów jest N wiec mamy N*log(N)
jeśli wykorzystamy std::unordered_set wówczas jest to faktycznie pewna nowa opcja nie opisana w poście.
Włożenie i usuniecie ma złożoność O(1) ale złożoność pamięciowa jest M(N).
Ten przypadek może nawet
@Bisk: zaleta seta jest taka ze nie alokujesz ogromnego obszaru pamięci nawet jak masz 20 elementów
czyli w Javie HashSet
zapewne jest to odpowiednik std::unordered_set w cpp
źródło: comment_Lxo4VMl1vN5nSyjiy5161eEh3EyHAvFr.jpg
Pobierz