Keskustelu: Ohjelmointiputka: Putkaposti 7: Junarata

Uusi putkapostitehtävä on ilmestynyt:
https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=junar

Tämä tehtävä on jälleen ohjelmointitaituri Ville Petterssonin käsialaa.

Tehtävästä voi tuttuun tapaan keskustella tässä.

Ja Pettersson arvatenkin ratkaisee sen ajassa O(n), muistilla O(1) ...

os kirjoitti:

Ja Pettersson arvatenkin ratkaisee sen ajassa O(n), muistilla O(1) ...

Valitettavasti en, nykyinen malliratkaisu on hätävaramallia O(n^2). O(n log n) -ratkaisu on kuitenkin mielestäni mahdollinen, vaikkakin hieman mutkikkaampi ohjelmoida.

Tuossahan tuo bruteforce vääntää. ;) Olisikohan siis O(n^3)...

O(n^2):lla meni muutama minuutti viimeisen vääntämiseen.

Mulla meni viimeiseen myös muutama minuutti. EDIT: 1min 20s ADM 2000+. Kahdeksanteen 10s. Mistä pystyy päättelemään onko tekoäly O(n^2) vai O(n^3)? Pitääkö siinä vaan koittaa eri kokosia haasteita, ja tutkia, nouseeko aika toisessa vai kolmannessa potenssissa?

Nyrkkisääntönä sisäkkäisten (for-)silmukoiden määrä kertoo eksponentin.

Esim. tässä on O(n^2)-algoritmi:

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        // jotain juttuja
    }
}

Näin voidaan laskea, missä suhteessa syötteen kokoon ohjelman ajankäyttö kasvaa. Esim. tässä tehtävässä n-muuttuja on numerotaulujen määrä.

Viimeisen syötteen ratkaisu tuossa ajassa kertoo siitä, että olet onnistunut keksimään O(n^2)-algoritmin.

Mutta mihin luokkaan kuuluu tällainen silmukka?

for (i = 0; i < n; ++i)
    for (j = 0; j < i; ++j)
        funktio();

Metabolix kirjoitti:

Mutta mihin luokkaan kuuluu tällainen silmukka?

Riippuu täysin siitä, miten monimutkainen funktio() on. Jos funktio() on vakioaikainen, niin silmukka on edelleen neliöllistä kompleksisuusluokkaa; funktiota kutsutaan n*(n-1)/2 = suunnilleen n*n/2 kertaa.

Hieman epämuodollisin merkinnöin ilmaistuna voisi kompleksisuusluokaksi ilmoittaa O(n^2*"funktion kompleksisuus").

IOI-valmennuksessa saamistasi kirjoista löytyy hyviä lukuja kompleksisuusluokan laskemisesta, niistä voit katsoa tarkemmin.

Minusta tuo kuuluu myös O(n^2)-luokkaan. Sisempi silmukka kiertää nimittäin keskimäärin n/2 kierrosta. Tästä syystä suoritusaika on kuitenkin vain puolet verrattuna minun silmukkaani. (Ville oli nopeampi.)

Miten ihmeessä tämä on mahdollista saada O(n²)-luokkaan, kun erilaisia järjestyksen vaihtotapoja on 0,5*(n²-n) ( O(n²) aikakompleksiivisuus ) enkä mitenkään keksi tapaa saada kierrosmäärän laskentaa radan pituudesta riippumattomaksi ( O(1) )?

Minä taas luulen keksineeni ehkä jopa tuon mainitun O(n log n)-luokkaisen, mutta sen toteuttaminen onkin sitten asia erikseen. Pitäisi varmaankin siirtyä käyttelemään paperia ja kynää.

L2-K2, musta tuntuu, että jos aikakompleksisuus olisi vaikka O(an^2-bn+c), niin sitä voidaan sanoa O(n^2), koska 2 on suurin potenssi kyseisessä polynomissa. Jos vaihtotavat saa selville 0,5*O(n^2) ajassa sekä sekä kierrosmäärän laskemisen ajassa O(1/500*n), niin sitä voi kutsua O(n^2) algoritmiksi. Minulla 9-radan kierrosten määrän laskemiseksi meni muistaakseni n. 160ms, jota ei juurikaan tarvi huomioida ajankulun laskemisessa, jos koko pulman laskemiseen menee reilusti yli minuutti.

Touho, mutta bruteforce-ratkaisuhan menee niin, että O(n^2)-silmukassa kierretään läpi kaikki vaihtoehdot, miten nuo voi vaihtaa, ja joka kerta lasketaan kierrosten lukumäärä O(n). Näistä tulee yhteensä O(n^3). Eihän sitä voi tietää, montako kierrosta vaihdon jälkeen on, jos sitä ei jotenkin laske. ;)

Oma bruteforce O(n^3) ratkaisuni muuttui pienellä vaivalla tuoksi lähes O(n^2) ratkaisuksi juuri kierrosten lukumäärän laskemistavan muutoksella (jonka sain suht vakioksi riippumatta radan koosta).

Riittää tähän tehtävään, vaikka toisaalta on tyhmää jos (viimeisen) radan laskemiseen menee yli 15 s. Olisin ehkä kaivannut vielä yhtä suurempaa rataa, vaikka en tiedä olisinko edes saanut sitä koskaan ratkaistua.

En tiedä, onko tämä jo liian vihjaavaa. Jos et halua saada yhtään mitään vinkkiä, älä lue tätä.

Metabolix, mun menetelmä ensin ratkaisen O(n^2) menetelmällä (tai 0.5*(n^2-n) vai mikä olikaan), mitkä taulut kannattaa siirtää. sen jälkeen katson, montako kierrosta menee saada ne kaikki. Tällöin ohjelma säilyttää O(n^2) ominaisuutensa.

Touho, kyllä minä tiedän, miten tuon voi ratkaista, mutta ennen kuin keksii tavan laskea kierrokset O(1)-ajassa vaihtojen välillä, joutuu sielläkin käyttämään tuota O(n)-laskutapaa.

Minä käytän kierrosten lasku -funktiota koko ohjelman suorituksen aikana vain kerran.