Egy vektor, két feladat

ekkor:

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.

12 gondolat erről “Egy vektor, két feladat

  1. A másodikat nem értem,mi egy lépés? O(n)-ben megoldható simán, de szerintem te nem erre gondolsz.

  2. Basszus. A masodikban az osszehasonlitasok szamanak kell ennyinek lenni. Trukkos de megoldhato.

  3. Ok, és átlagos, vagy legrosszabb esetben? Előbbire van egyszerű algoritmusom, nemtrükkös, de legrosszabb esetben 2n hasonlítást csinál.

  4. 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.

  5. 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?

  6. Az elsőnél elég 1x végigmenni a vektoron. A másodiknál Lőry plasztikus megfogalmazása nagyon jó szerintem.

Hozzászólás letiltva