Trebam informacija o takozvanoj logaritamskoj strukturi.
Hvala.
Hvala.
Logaritamska struktura
Zaključano
Zakačeno
izmenjeno 1 put, poslednji put emiraga 13.05.2006. u 16:40
Izmene poruke
- emiraga13.05.2006. u 16:40zapis iz teksta poruke
Ja se nadam da mislis na Kumulativne sume sa logaritamkom strukturom
evo o jednog topic-a
https://www.elitesecurity.org/t80503
u njemu ima link do dobrog pdf-a
http://www.cs.ubc.ca/local/rea...95/spe/vol24/issue3/spe884.pdf
ideja je da se brzina _citanja_ elemenata iz kumulativne sume _uspori_
u zamjenu da se brzina _promjene_ neke vrijednosti _ubrza_
i to sa obje kompleksnosti
evo o jednog topic-a
https://www.elitesecurity.org/t80503
u njemu ima link do dobrog pdf-a
http://www.cs.ubc.ca/local/rea...95/spe/vol24/issue3/spe884.pdf
ideja je da se brzina _citanja_ elemenata iz kumulativne sume _uspori_
u zamjenu da se brzina _promjene_ neke vrijednosti _ubrza_
i to sa obje kompleksnosti
znam sigurno da logaritamska struktura ima za citanje i upisivanje
pogledati cu linkove pa javim
za citanje i upisivanjepogledati cu linkove pa javim
Je to je bilo to, hvala.
Ja to radim ovako..Ponekad se moze prilagoditi da bude optimalnije od Kum. Tab.
kao recimo u zadatku "reli" sa saveznog ove godine..
Sa kum.tab. treba obaviti n*2*log(n) a na "moj" nacin n*log(n) + n
//INACE!
//U Reli-ju
kao recimo u zadatku "reli" sa saveznog ove godine..
Sa kum.tab. treba obaviti n*2*log(n) a na "moj" nacin n*log(n) + n
//INACE!
Code:
void set(int x){
l=1,r=n;
do{
m=(l+r)>>1; // m=(l+r)/2;
if(x<=m){
A[m]++;
r=m-1;
}else
l=m+1;
}while(l<=r && m!=x);
}
int get(int x){
l=1,r=n,tr=0;
do{
m=(l+r)>>1; // m=(l+r)/2;
if(x>=m){
tr+=A[m];
l=m+1;
}else
r=m-1;
}while(l<=r && m!=x);
return tr;
}
void set(int x){
l=1,r=n;
do{
m=(l+r)>>1; // m=(l+r)/2;
if(x<=m){
A[m]++;
r=m-1;
}else
l=m+1;
}while(l<=r && m!=x);
}
int get(int x){
l=1,r=n,tr=0;
do{
m=(l+r)>>1; // m=(l+r)/2;
if(x>=m){
tr+=A[m];
l=m+1;
}else
r=m-1;
}while(l<=r && m!=x);
return tr;
}
//U Reli-ju
Code:
int getset(int x){
l=1,r=n,tr=0;
do{
m=(l+r)>>1;
if(x<=m){
A[m]++;
r=m-1;
}else{
tr+=A[m];
l=m+1;
}
}while(l<=r && m!=x);
return tr;
}
int getset(int x){
l=1,r=n,tr=0;
do{
m=(l+r)>>1;
if(x<=m){
A[m]++;
r=m-1;
}else{
tr+=A[m];
l=m+1;
}
}while(l<=r && m!=x);
return tr;
}
Potpis
Ljubav je kad ja prdnem a njoj ne smrdi.
I na DMIH-u je ove godine bio zadatak koji se rijesava kumulativnim tablicama.
Sta su zapeli za to?! :)
Sta su zapeli za to?! :)
Reli nije morao da se reshava kumulativnim tablicama (ja sam ga radio kao merge sort).
A ovaj sa dmih (3. zadatak drugog dana ako se dobro secam) se slazem da najjednostavnije ide preko ktabela ...
A ovaj sa dmih (3. zadatak drugog dana ako se dobro secam) se slazem da najjednostavnije ide preko ktabela ...
Potpis
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
e, nije sex nego serem!
Citat:
RooTeR:A ovaj sa dmih (3. zadatak drugog dana ako se dobro secam) se slazem da najjednostavnije ide preko ktabela ...
Citat:
RooTeR: Reli nije morao da se reshava kumulativnim tablicama (ja sam ga radio kao merge sort).
Znam da nije morao.
Posuzio mi je kao primer..
Potpis
Ljubav je kad ja prdnem a njoj ne smrdi.
HAHAHAHAHAHA, evo kezim se dok gledam sta vi uzimate kao primer za kumulativne sume. Inace, reli moze da se uradi na jedno osam nacina... merge sort, stane u 10 redova. A ja sam svima koji urade reli obecao COKOLADU! Dobar primer za primenu kumulativnih suma je jedan zadatak sa mobilnom mrezom sa olimpijade iz finske 2002. Koga interesuje neka gugla, zadatak koristi 2D kumulativne sume i extra je. Inace, finci su te godine izdali bilten sa svim zadacima i svim PREDLOZIMA i ko hoce moze da nauci masu fora iz tog pdfa.
A ko je uradio reli koristeci merge sort, dobio je dve chokolade :) (bar sam ja dobio:)
Potpis
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
e, nije sex nego serem!