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.
A másodikat nem értem,mi egy lépés? O(n)-ben megoldható simán, de szerintem te nem erre gondolsz.
Basszus. A masodikban az osszehasonlitasok szamanak kell ennyinek lenni. Trukkos de megoldhato.
Ok, és átlagos, vagy legrosszabb esetben? Előbbire van egyszerű algoritmusom, nemtrükkös, de legrosszabb esetben 2n hasonlítást csinál.
Legrosszabb
Hm. Az tényleg trükkösen hangzik.
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.
Mármint a második szakaszban egy minker természetesen.
Ahemm. :)
Jólvanna. És köszi a képletesítést.
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?
Lőry és azt hogy biztosítod, hogy P <= Q legyen?
Az elsőnél elég 1x végigmenni a vektoron. A másodiknál Lőry plasztikus megfogalmazása nagyon jó szerintem.