Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 49 ]  Przejdź na stronę Poprzednia strona  1, 2, 3, 4, 5
Przedzialy - testy 
Autor Wiadomość
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 20 lis 2009, o 18:40
Posty: 105
Post Re: Przedzialy - testy
Cytuj:
Po prostu najpierw pomyslalem, ze moze dzialac, potem zaczelem sie zastanawiac nad jego poprawnoscia...

1. Robimy 2 posortowane, niezalezne tablice: 1. okresla poczatki wsyzstkich przedzialow, konce + zmienną minp = pocz[0]
3. Lecimy petla i ustawiamy i = 1 < n, jesli w pewnym momencie zachodzi wlasnosc: pocz[i] > kon[i-1], to dodajemy do wyniku wartosc kon[i]-minp+1;
4. Ustawiamy minp jako pocz[i] i lecimy dalej...
5. I na koniec jeszcze dodajemy kon[n-1]-minp+1

Czyli po prostu, jesli przedzialy sie nachodza, "laczymy" je w jeden i sumujemy wartosci dla polaczonych. minp okresla nam zawsze poczatek tego polaczonego, z ktorym aktulanie mamy do czynienia


No to mi się wydaje że to jest algorytm oczywisty i chyba każdy mniej więcej tak robił. Nie wiem jakie tu można mieć wątpliwości co do poprawności. :P

@UP: Liniówki się raczej nie dało :P


15 paź 2010, o 23:43
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 17 lis 2009, o 17:54
Posty: 29
Post Re: Przedzialy - testy
Ja mam O(n) nie liczac sorta - czyli prawie O(n) ;)

Cytuj:
No to mi się wydaje że to jest algorytm oczywisty i chyba każdy mniej więcej tak robił. Nie wiem jakie tu można mieć wątpliwości co do poprawności. :P

Jak człowiek zmeczony, to i tak potrafi :)


Ostatnio edytowano 15 paź 2010, o 23:45 przez Tomasz Kotarski, łącznie edytowano 1 raz



15 paź 2010, o 23:43
Zobacz profil
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 20 lis 2009, o 18:40
Posty: 105
Post Re: Przedzialy - testy
Cytuj:
Ja mam O(n) nie liczac sorta - czyli prawie O(n) ;)


Ja mam O(1) nie licząc całego algorytmu.


15 paź 2010, o 23:45
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: Przedzialy - testy
No ale jak ktoś chce, to zawsze może posortować przez zliczanie teoretycznie w czasie liniowym :P.


15 paź 2010, o 23:53
Zobacz profil
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 20 lis 2009, o 18:40
Posty: 105
Post Re: Przedzialy - testy
Tia. Liniowym do 2*10^9. :P
Nie wspominając o pamięci :D


15 paź 2010, o 23:58
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: Przedzialy - testy
Nie mówię o sortowaniu kubełkowym, tylko o sortowaniu przez zliczanie, które pozwala nam sortować liczby nie przekraczające n w złożoności czasowej i pamięciowej O(\sqrt{n}), dzięki czemu możemy w rozsądnym czasie i pamięci posortować liczby do 10^{12}.


16 paź 2010, o 00:06
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 20 lis 2009, o 14:15
Posty: 106
Post Re: Przedzialy - testy
Nie cwaniakować tylko pisać ;>


16 paź 2010, o 00:29
Zobacz profil
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 20 lis 2009, o 18:40
Posty: 105
Post Re: Przedzialy - testy
Ja znam zliczanie co działa w czasie O(x) gdzie x to największa z liczb do posortowania. O tym z pierwiastkiem pierwsze słyszę. O.o


16 paź 2010, o 01:51
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 23 lis 2009, o 23:00
Posty: 101
Post Re: Przedzialy - testy
Kod:

Test    Wynik   Czas    Pamięć
0.out (test przykładowy)   accepted    0.00s   1004
1.out   accepted    0.00s   1004
2.out   accepted    0.00s   1004
3.out   accepted    0.00s   1004
4.out   accepted    0.00s   1004
5.out   accepted    0.00s   1004
6.out   accepted    0.40s   7144
7.out   accepted    0.39s   5096
8.out   accepted    0.55s   25580
9.out   accepted    0.47s   13292
10.out  accepted    0.25s   4076
 


16 paź 2010, o 09:03
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 49 ]  Przejdź na stronę Poprzednia strona  1, 2, 3, 4, 5


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 2 gości


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Szukaj:
Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL