N1
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View N1 as PDF for free.
More details
- Words: 1,448
- Pages: 6
1.
Mediánok és rendezett minták
Kiválasztási probléma ˝ elemek H = {a1 , . . . , an } halmaza, amelyeken értelmezett egy ≤ lineáris rendezési reláció Bemenet: Azonos típusú (különbözo) és egy k (1 ≤ k ≤ n) index. Kimenet: Olyan x ∈ H , hogy |{y : y ∈ H ∧ y ≤ x}| = k. A kimenetben szereplo˝ x-et a H rendezett minta k-adik (legkisebb) elemének nevezzük. A középso˝ elemet a rendezett minta mediánjának nevezzük. Pontosabban, az k = b(n + 1)/2c-edik elem az alsó, az k = d(n + 1)/2e-edik elem a felso˝ medián.
1.1.
Minimum és maximum egyideju˝ meghatározása.
Adott A = ha0 , . . . , an−1 i (nem rendezett) sorozatból válasszuk ki a legkisebb és a legnagyobb elemet.
public <E extends Comparable<E>>void MiniMax(E[] A, Integer mini, Integer maxi){ int n=A.length; int k; if (n%2==0){ k=2; if (A[0].compareTo(A[1])<0){ mini=0; maxi=1; }else{ mini=1; maxi=0; } }else{ k=1; mini=0; maxi=0; } for (int i=k; i+1
1.2.
Kiválasztás ismételt felosztással (iterált particionálás)
Elvi algoritmus:
Valaszt(H:Halmaz, k:Longint):Elemtip; {1 ≤ k ≤ |H|} Var Hb , H j :Halmaz; x:Elemtip; Begin{Valaszt} If |H| = 1 Then Begin Valaszt:=x (* H = {x} *); End Else Begin; Feloszt(H, Hb , H j , x);
{H = Hb ∪ H j ∪ {x}, max(Hb ) ≤ x < min(H j )} q := |Hb |; If k ≤ q Then Valaszt:=Valaszt(Hb , k); Else If k > q + 1 Then Valaszt:=Valaszt(H j , k − q − 1); Else Valaszt:=x End{|H| > 1};
1
End{Valaszt};
public static <E extends Comparable<E>> int FKivalaszt(E[] a, int k){ int bal=0; int jobb=a.length-1; int f; if (k<0 || k>jobb) return -1; while (bal<jobb) { f=Rendez.Feloszt(a, bal, jobb); if (k<=f-bal) jobb=f-1; else if (k>f-bal+1){ k-=(f-bal+1); bal=f+1; }else return f; } return bal; } A futási ido˝ elemzése. Tlr (n) = O(n2 ), lásd a gyorsrendezés legrosszabb esetét. Tl j (n) = O(n). Átlagos eset Feltesszük, hogy minden bemenet egyformán valószínu. ˝ Az f felosztó index lehetséges értékei:
= 0, 1, · · · , n − 2, n − 1
f
A keresés vagy a bal oldali részben folytatódik, amelynek hossza ekkor f , vagy a jobboldaliban, amelynek hossza n − f − 1. (A ˝ keresés befejezodik, ha a keresett elem éppen a felosztó elem.) Feltéve, hogy Ta (n) monoton növekvo˝ függvény,
Ta (n) ≤
1 n
n−1
∑ Ta (max( f , n − f − 1)) + O(n)
f =0
˝ n − 1-ig kétszer szerepel az összegMivel a felosztás ideje O(n). Ha n páros, akkor a max kifejezés mindkét argumentuma 1-tol zésben, ha n páratlan, akkor pedig bn/2c egyszer, a többi kétszer. Tehát
max( f , n − f − 1) =
Ta (n) ≤
2 n
f n− f −1
ha f > dn/2e , ha f ≤ dn/2e .
n−1
∑
Ta ( f ) + O(n)
f =bn/2c
2
Tegyük fel, hogy van olyan c konstans, hogy Ta (n) ≤ c n és hogy c teljesíti a rekurzív képlet kezdeti feltételét, azaz T (n) = O(1) valamely konstansnál kisebb n-ekre. Tegyük fel továbbá, hogy a felosztás futási idejét kifejezo˝ O(n) tagra teljesül, hogy ≤ a n.
Ta (n) ≤
= = ≤ = = = ≤ =
2 n
n−1
∑
c f + an
f =bn/2c
2c n
∑
f−
f =1
!
bn/2c−1
n−1
∑
f
+ an
f =1
2c (n − 1)n (bn/2c − 1) bn/2c − + an n 2 2 2c (n − 1)n (n/2 − 2)(n/2 − 1) − + an n 2 2 2c n2 − n n2 /4 − 3n/2 + 2 − + an n 2 2 c 3n2 n + − 2 + an n 4 2 3n 1 2 c + − + an 4 2 n 3cn c + + an 4 2 cn c cn − − − an . 4 2
Más csak azt kell megmutatnunk, hogy elég nagy n-ekre a fenti kifejezés legfeljebb cn, ami ekvivalens azzal, hogy cn/4 − c/2 − a n ≥ 0. Mindkét oldalhoz c/2-t adva és kiemelve n-et, azt kapjuk, hogy n(c/4 − a) ≥ c/2. Ha a c konstanst úgy választjuk, hogy c/4 − a > 0, vagyis c > 4a, oszthatunk c/4 − a-val, és kapjuk
n≥
c/2 2c = . c/4 − a c − 4a
Tehát feltéve, hogy Ta (n) = O(1) ha n < 2c/(c − 4a), azt kapjuk, hogy
Ta (n) = O(n).
1.3.
˝ Kiválasztás legrosszabb esetben lineáris idoben
Alapötlet: a felosztó elem "jó" választása. LinKiValaszt(H:Halmaz, k:Longint):Elemtip; {1 ≤ k ≤ |H|} Var Hb , H j :Halmaz; Begin{LinKiValaszt} If |H| = 1 Then Begin LinKiValaszt:=x (* H = {x} *); End Else Begin; L := N div 5; H = H1 + · · · + HL + HL+1 ; {ötös csoportok} {|Hi | = 5, i = 1..L, |HL+1 | < 5 }; Med5 := {Valaszt(H1 , 3), · · · ,Valaszt(HL , 3)}; Fe := LinKiValaszt(Med5, L/2); Feloszt(H, Fe, Hb , x, H j ); {felosztás az Fe felosztó elemmel} {max(Hb ) ≤ x < min(H j )} q := |Hb |; If k = q + 1 Then LinKiValaszt:=x; Else If k ≤ q Then LinKiValaszt:=LinKiValaszt(Hb , k); Else Begin{q + 1 < k} LinKiValaszt:=LinKiValaszt(H j , k − q − 1);
3
End; End{LinKiValaszt};
A futási ido˝ elemzése Képzeljük el, hogy rendeztük az ötös csoportokat, majd ezeket a középso˝ elemük szerint. Ezt szemlélteti az 1. ábra.
Az ábrán
Fe
1. ábra. Az ötös csoportok szerepe a felosztásban. ˝ mint az Fe felosztó elem, a feketék pedig nagyobbak, mint Fe. szürkére festett elemek mindegyike kisebb vagy egyenlo,
l m 1 n 3n q = |Hb | ≥ 3 −2 ≥ −6 2 5 10 Tegyük fel, hogy a legfeljebb 140 elemu˝ bemenetekre a futási ido˝ Θ(1). Ekkor, mivel a felosztás ideje O(n), azt kapjuk, hogy
Tlr (n) ≤
Θ(1) Tlr (dn/5e) + Tlr (7n/10 + 6) + O(n)
ha n ≤ 140 , ha n > 140 .
Tegyük fel továbbá, hogy a felosztás futási idejét kifejezo˝ O(n) tagra teljesül, hogy ≤ a n valamely a konstansra. Tehát
Tlr (n) ≤ c dn/5e + c(7n/10 + 6) + an ≤ cn/5 + c + 7cn/10 + 6c + an = 9cn/10 + 7c + an = cn + (−cn/10 + 7c + an) , amely legfeljebb cn, ha
−cn/10 + 7c + an ≤ 0 .
(1)
˝ Az (1) egyenlotlenség teljesül, ha c ≥ 10a(n/(n − 70)) és n > 70. Mivel feltettük, hogy n ≥ 140, kapjuk, hogy n/(n − 70) ≤ 2, és ˝ így c ≥ 20a választása esetén teljesül a kívánt egyenlotlenség , tehát Tlr (n) = O(n). Megvalósítás
public static <E extends Comparable<E> > int LinKivalaszt(E[] a, int k){ return valaszt(a,0,a.length-1,k); } private static <E extends Comparable<E> > int valaszt(E[] a, int bal,int jobb, int k){ int R0 = 2; int R = 2*R0+1; int m, L, f; do{ m=jobb-bal+1; L=m/R; if (m<=R){ BeszuroRend(a, bal, m, 1); return bal+k-1; }else{ for (int i=1; i<=L; i++) BeszuroRend(a, bal+i-1, R, L); f= valaszt(a, bal+R0*L, bal+(R0+1)*L-1, L/2); 4
f=Feloszt(a, bal, jobb, f); if (k<=f-bal) jobb=f-1; else if (k>f-bal+1){ k-=(f-bal+1); bal=f+1; }else return f; } }while(true); } private static <E extends Comparable<E> > void BeszuroRend(E[] a, int elso, int elemszam, int d) { int i=elso+d; int utolso=elso+(elemszam-1)*d; int j; E e; while (i<=utolso){ e = a[i]; j=i-d; while(j>=elso && e.compareTo(a[j])<0){ a[j+d]=a[j]; j-=d; } a[j+d]=e; i+=d; } } private static <E extends Comparable<E> > int Feloszt(E[]a, int bal, int jobb, int E fe =a[f]; a[f]=a[bal];
f){
while (bal<jobb) { int p = bal; for (int r = bal+1; r <= jobb; r++) { if (a[r].compareTo(fe) < 0) { a[p] = a[r]; a[r] = a[++p]; } } a[p] = fe; return p; } return bal; }
1.4.
Kiválasztás kupaccal
A L IN K IVALASZT algoritmus ugyan legrosszabb esetben is lineáris futási ideju, ˝ azonban az O(n) kifejezésben a konstans elég nagy. Kis i-re gyorsabb algoritmust adhatunk kupac alkalmazásával.
public static <E extends Comparable<E> > int KupacValaszt(E[] a, int k){ int n=a.length-1; E e; for (int i=k/2; i>0; i--) Sullyeszt(a, i, k);
5
//
for (int i=k+1; i<=n; i++) Invariáns: a[1] a tömb a[1..i] elemei közül az k-adik legkisebb if (a[i].compareTo(a[1])<0){ e=a[1]; a[1]=a[i]; a[i]=e; Sullyeszt(a, 1, k); } return 1;
} A K UPAC VALASZT algoritmus futási ideje: Tlr (n) = O(k) + (n − k)O(lg k).
6
Mediánok és rendezett minták
Kiválasztási probléma ˝ elemek H = {a1 , . . . , an } halmaza, amelyeken értelmezett egy ≤ lineáris rendezési reláció Bemenet: Azonos típusú (különbözo) és egy k (1 ≤ k ≤ n) index. Kimenet: Olyan x ∈ H , hogy |{y : y ∈ H ∧ y ≤ x}| = k. A kimenetben szereplo˝ x-et a H rendezett minta k-adik (legkisebb) elemének nevezzük. A középso˝ elemet a rendezett minta mediánjának nevezzük. Pontosabban, az k = b(n + 1)/2c-edik elem az alsó, az k = d(n + 1)/2e-edik elem a felso˝ medián.
1.1.
Minimum és maximum egyideju˝ meghatározása.
Adott A = ha0 , . . . , an−1 i (nem rendezett) sorozatból válasszuk ki a legkisebb és a legnagyobb elemet.
public <E extends Comparable<E>>void MiniMax(E[] A, Integer mini, Integer maxi){ int n=A.length; int k; if (n%2==0){ k=2; if (A[0].compareTo(A[1])<0){ mini=0; maxi=1; }else{ mini=1; maxi=0; } }else{ k=1; mini=0; maxi=0; } for (int i=k; i+1
1.2.
Kiválasztás ismételt felosztással (iterált particionálás)
Elvi algoritmus:
Valaszt(H:Halmaz, k:Longint):Elemtip; {1 ≤ k ≤ |H|} Var Hb , H j :Halmaz; x:Elemtip; Begin{Valaszt} If |H| = 1 Then Begin Valaszt:=x (* H = {x} *); End Else Begin; Feloszt(H, Hb , H j , x);
{H = Hb ∪ H j ∪ {x}, max(Hb ) ≤ x < min(H j )} q := |Hb |; If k ≤ q Then Valaszt:=Valaszt(Hb , k); Else If k > q + 1 Then Valaszt:=Valaszt(H j , k − q − 1); Else Valaszt:=x End{|H| > 1};
1
End{Valaszt};
public static <E extends Comparable<E>> int FKivalaszt(E[] a, int k){ int bal=0; int jobb=a.length-1; int f; if (k<0 || k>jobb) return -1; while (bal<jobb) { f=Rendez.Feloszt(a, bal, jobb); if (k<=f-bal) jobb=f-1; else if (k>f-bal+1){ k-=(f-bal+1); bal=f+1; }else return f; } return bal; } A futási ido˝ elemzése. Tlr (n) = O(n2 ), lásd a gyorsrendezés legrosszabb esetét. Tl j (n) = O(n). Átlagos eset Feltesszük, hogy minden bemenet egyformán valószínu. ˝ Az f felosztó index lehetséges értékei:
= 0, 1, · · · , n − 2, n − 1
f
A keresés vagy a bal oldali részben folytatódik, amelynek hossza ekkor f , vagy a jobboldaliban, amelynek hossza n − f − 1. (A ˝ keresés befejezodik, ha a keresett elem éppen a felosztó elem.) Feltéve, hogy Ta (n) monoton növekvo˝ függvény,
Ta (n) ≤
1 n
n−1
∑ Ta (max( f , n − f − 1)) + O(n)
f =0
˝ n − 1-ig kétszer szerepel az összegMivel a felosztás ideje O(n). Ha n páros, akkor a max kifejezés mindkét argumentuma 1-tol zésben, ha n páratlan, akkor pedig bn/2c egyszer, a többi kétszer. Tehát
max( f , n − f − 1) =
Ta (n) ≤
2 n
f n− f −1
ha f > dn/2e , ha f ≤ dn/2e .
n−1
∑
Ta ( f ) + O(n)
f =bn/2c
2
Tegyük fel, hogy van olyan c konstans, hogy Ta (n) ≤ c n és hogy c teljesíti a rekurzív képlet kezdeti feltételét, azaz T (n) = O(1) valamely konstansnál kisebb n-ekre. Tegyük fel továbbá, hogy a felosztás futási idejét kifejezo˝ O(n) tagra teljesül, hogy ≤ a n.
Ta (n) ≤
= = ≤ = = = ≤ =
2 n
n−1
∑
c f + an
f =bn/2c
2c n
∑
f−
f =1
!
bn/2c−1
n−1
∑
f
+ an
f =1
2c (n − 1)n (bn/2c − 1) bn/2c − + an n 2 2 2c (n − 1)n (n/2 − 2)(n/2 − 1) − + an n 2 2 2c n2 − n n2 /4 − 3n/2 + 2 − + an n 2 2 c 3n2 n + − 2 + an n 4 2 3n 1 2 c + − + an 4 2 n 3cn c + + an 4 2 cn c cn − − − an . 4 2
Más csak azt kell megmutatnunk, hogy elég nagy n-ekre a fenti kifejezés legfeljebb cn, ami ekvivalens azzal, hogy cn/4 − c/2 − a n ≥ 0. Mindkét oldalhoz c/2-t adva és kiemelve n-et, azt kapjuk, hogy n(c/4 − a) ≥ c/2. Ha a c konstanst úgy választjuk, hogy c/4 − a > 0, vagyis c > 4a, oszthatunk c/4 − a-val, és kapjuk
n≥
c/2 2c = . c/4 − a c − 4a
Tehát feltéve, hogy Ta (n) = O(1) ha n < 2c/(c − 4a), azt kapjuk, hogy
Ta (n) = O(n).
1.3.
˝ Kiválasztás legrosszabb esetben lineáris idoben
Alapötlet: a felosztó elem "jó" választása. LinKiValaszt(H:Halmaz, k:Longint):Elemtip; {1 ≤ k ≤ |H|} Var Hb , H j :Halmaz; Begin{LinKiValaszt} If |H| = 1 Then Begin LinKiValaszt:=x (* H = {x} *); End Else Begin; L := N div 5; H = H1 + · · · + HL + HL+1 ; {ötös csoportok} {|Hi | = 5, i = 1..L, |HL+1 | < 5 }; Med5 := {Valaszt(H1 , 3), · · · ,Valaszt(HL , 3)}; Fe := LinKiValaszt(Med5, L/2); Feloszt(H, Fe, Hb , x, H j ); {felosztás az Fe felosztó elemmel} {max(Hb ) ≤ x < min(H j )} q := |Hb |; If k = q + 1 Then LinKiValaszt:=x; Else If k ≤ q Then LinKiValaszt:=LinKiValaszt(Hb , k); Else Begin{q + 1 < k} LinKiValaszt:=LinKiValaszt(H j , k − q − 1);
3
End; End{LinKiValaszt};
A futási ido˝ elemzése Képzeljük el, hogy rendeztük az ötös csoportokat, majd ezeket a középso˝ elemük szerint. Ezt szemlélteti az 1. ábra.
Az ábrán
Fe
1. ábra. Az ötös csoportok szerepe a felosztásban. ˝ mint az Fe felosztó elem, a feketék pedig nagyobbak, mint Fe. szürkére festett elemek mindegyike kisebb vagy egyenlo,
l m 1 n 3n q = |Hb | ≥ 3 −2 ≥ −6 2 5 10 Tegyük fel, hogy a legfeljebb 140 elemu˝ bemenetekre a futási ido˝ Θ(1). Ekkor, mivel a felosztás ideje O(n), azt kapjuk, hogy
Tlr (n) ≤
Θ(1) Tlr (dn/5e) + Tlr (7n/10 + 6) + O(n)
ha n ≤ 140 , ha n > 140 .
Tegyük fel továbbá, hogy a felosztás futási idejét kifejezo˝ O(n) tagra teljesül, hogy ≤ a n valamely a konstansra. Tehát
Tlr (n) ≤ c dn/5e + c(7n/10 + 6) + an ≤ cn/5 + c + 7cn/10 + 6c + an = 9cn/10 + 7c + an = cn + (−cn/10 + 7c + an) , amely legfeljebb cn, ha
−cn/10 + 7c + an ≤ 0 .
(1)
˝ Az (1) egyenlotlenség teljesül, ha c ≥ 10a(n/(n − 70)) és n > 70. Mivel feltettük, hogy n ≥ 140, kapjuk, hogy n/(n − 70) ≤ 2, és ˝ így c ≥ 20a választása esetén teljesül a kívánt egyenlotlenség , tehát Tlr (n) = O(n). Megvalósítás
public static <E extends Comparable<E> > int LinKivalaszt(E[] a, int k){ return valaszt(a,0,a.length-1,k); } private static <E extends Comparable<E> > int valaszt(E[] a, int bal,int jobb, int k){ int R0 = 2; int R = 2*R0+1; int m, L, f; do{ m=jobb-bal+1; L=m/R; if (m<=R){ BeszuroRend(a, bal, m, 1); return bal+k-1; }else{ for (int i=1; i<=L; i++) BeszuroRend(a, bal+i-1, R, L); f= valaszt(a, bal+R0*L, bal+(R0+1)*L-1, L/2); 4
f=Feloszt(a, bal, jobb, f); if (k<=f-bal) jobb=f-1; else if (k>f-bal+1){ k-=(f-bal+1); bal=f+1; }else return f; } }while(true); } private static <E extends Comparable<E> > void BeszuroRend(E[] a, int elso, int elemszam, int d) { int i=elso+d; int utolso=elso+(elemszam-1)*d; int j; E e; while (i<=utolso){ e = a[i]; j=i-d; while(j>=elso && e.compareTo(a[j])<0){ a[j+d]=a[j]; j-=d; } a[j+d]=e; i+=d; } } private static <E extends Comparable<E> > int Feloszt(E[]a, int bal, int jobb, int E fe =a[f]; a[f]=a[bal];
f){
while (bal<jobb) { int p = bal; for (int r = bal+1; r <= jobb; r++) { if (a[r].compareTo(fe) < 0) { a[p] = a[r]; a[r] = a[++p]; } } a[p] = fe; return p; } return bal; }
1.4.
Kiválasztás kupaccal
A L IN K IVALASZT algoritmus ugyan legrosszabb esetben is lineáris futási ideju, ˝ azonban az O(n) kifejezésben a konstans elég nagy. Kis i-re gyorsabb algoritmust adhatunk kupac alkalmazásával.
public static <E extends Comparable<E> > int KupacValaszt(E[] a, int k){ int n=a.length-1; E e; for (int i=k/2; i>0; i--) Sullyeszt(a, i, k);
5
//
for (int i=k+1; i<=n; i++) Invariáns: a[1] a tömb a[1..i] elemei közül az k-adik legkisebb if (a[i].compareTo(a[1])<0){ e=a[1]; a[1]=a[i]; a[i]=e; Sullyeszt(a, 1, k); } return 1;
} A K UPAC VALASZT algoritmus futási ideje: Tlr (n) = O(k) + (n − k)O(lg k).
6
