Egy vektor, két feladat
Adott egy \(n\) elemű egész számokat tartalmazó \(A\) vektor.
1. Adjuk meg azt a \(P\) és \(Q\) indexet, ami maximalizálja a \(sum_{i=P}^{Q}A[i]\) részvektort. Az algoritmus műveletideje legyen \(O(n)\).
2. Válasszuk ki a vektor második legkisebb elemét \(n + O(log_{2}n)\) összehasonlítással.
Mondta Maya ekkor: 2009. október 3., 21:39 link
A másodikat nem értem,mi egy lépés? O(n)-ben megoldható simán, de szerintem te nem erre gondolsz.
Mondta Encse ekkor: 2009. október 4., 08:38 link
Basszus. A masodikban az osszehasonlitasok szamanak kell ennyinek lenni. Trukkos de megoldhato.
Mondta Maya ekkor: 2009. október 4., 11:42 link
Ok, és átlagos, vagy legrosszabb esetben? Előbbire van egyszerű algoritmusom, nemtrükkös, de legrosszabb esetben 2n hasonlítást csinál.
Mondta Encse ekkor: 2009. október 4., 12:35 link
Legrosszabb
Mondta Maya ekkor: 2009. október 4., 20:56 link
Hm. Az tényleg trükkösen hangzik.
Mondta Maya ekkor: 2009. október 6., 12:38 link
A 2-esre a megoldásom: páronként kiemelejük a kisebb elemet, az eredményvektorból (mely fele olyan hosszú mint [latex]A[/latex]) ismét és ezt folyatjuk amíg egy elem nem marad, az a legkisebb (lk). Ez eddig [latex]n-1[/latex] hasonlítás (ha [latex]n[/latex] 2 hatvány, ezt feltételezzük az egyszerűség kedvéért). lk utolsó párja a második legkisebb, kivéve, ha valamelyik előző párja lk-nak kisebb nála, ez szintenként még egy azaz [latex]log_2(n)-1[/latex] db hasonlítás. Kész.
Mondta Maya ekkor: 2009. október 6., 13:04 link
Mármint a második szakaszban egy minker természetesen.
Mondta Encsé ekkor: 2009. október 6., 13:06 link
Ahemm. :)
Mondta Maya ekkor: 2009. október 6., 14:31 link
Jólvanna. És köszi a képletesítést.
Mondta Lőry ekkor: 2009. október 7., 15:32 link
2-es plasztikusabban megfogalmazva: hogyan kaphatjuk meg a második legjobb csapatot egy n résztvevős kieséses bajnokság eredményfájából? (Rendezzünk egy új kieséses bajnokságot a bajnok (log(n) db) korábbi ellenfelei között.)
1-es két futóösszeg-számolás, aztán két minker, ugye?
Mondta Maya ekkor: 2009. október 7., 20:00 link
Lőry és azt hogy biztosítod, hogy P <= Q legyen?
Mondta Encsé ekkor: 2009. október 7., 20:30 link
Az elsőnél elég 1x végigmenni a vektoron. A másodiknál Lőry plasztikus megfogalmazása nagyon jó szerintem.