Yleisesti lajittelualgoritmien (parhaiden)
aikavaatimus on aikaluokkaa O(n log n) missä n lajiteltavien objektien määrä ja aika lasketaan vertailujen lukumääränä.
Tämä on siis pahimman tapauksn aikavaatimus.
Mutta onko kukaan tehnyt laajempia tutkimuksia jonkin tietyn algoritmin kulutetuista ajoista.
Helppo on itsekin tehdä pienen n arvoilla n==100, se vaatisi 100! eri permuutaation järjestämistä ja ajan mittaamista. Tähän ei vain aika riitä ja permutaatioidenkin läpikäyminen on mahdotonta (brute forcella).
Eli onko menetelmää analyyttiseen jakauman selvittämiseen (approksimaatiokin kelpaa, eli jos keskeinen raja-lause on käyttökelpoinen niin..). Mutta tässä loppuu oma tietämys aiheesta!!!
Eli kiinoiistaisi jakaumat jollekin algoritmille, esim. 6 alkion mittaisen listan järjestykseen kuluva aika vertailuina. 6!=720 permutaatiosta selvisi
Vertailujen Kappaletta
määrä permutaatioista
1 2
2 3
3 8
jne.
(luvut hatusta!!!!)
aikavaatimus on aikaluokkaa O(n log n) missä n lajiteltavien objektien määrä ja aika lasketaan vertailujen lukumääränä.
Tämä on siis pahimman tapauksn aikavaatimus.
Mutta onko kukaan tehnyt laajempia tutkimuksia jonkin tietyn algoritmin kulutetuista ajoista.
Helppo on itsekin tehdä pienen n arvoilla n==100, se vaatisi 100! eri permuutaation järjestämistä ja ajan mittaamista. Tähän ei vain aika riitä ja permutaatioidenkin läpikäyminen on mahdotonta (brute forcella).
Eli onko menetelmää analyyttiseen jakauman selvittämiseen (approksimaatiokin kelpaa, eli jos keskeinen raja-lause on käyttökelpoinen niin..). Mutta tässä loppuu oma tietämys aiheesta!!!
Eli kiinoiistaisi jakaumat jollekin algoritmille, esim. 6 alkion mittaisen listan järjestykseen kuluva aika vertailuina. 6!=720 permutaatiosta selvisi
Vertailujen Kappaletta
määrä permutaatioista
1 2
2 3
3 8
jne.
(luvut hatusta!!!!)
Vastaukset 2
Vanhimmat
Aikooko täti kehittää uuden algoritmin vai vertailla olemassaolevia?
Googlettamalla luulisi löytyvän vertailutietoa. Ja voihan valmiita ohjelmia imuroida ja kokeilla itse, paljonko aikaa kuluu. Testitiedot voi tallentaa ja katsoa, noudattavatko ne esim. normaalijakaumaa.
Tuontyyppisten taksonomisten tehokkuusvertailujen tekemiseen ei taida löytyä oikotietä: ne permutaatiot/kombinaatiot on laskettava läpi, ellei jotain pysty etukäteen rajoittamaan eliminoitavaksi. Tällöin laskentatehokkuden ratkaiseen ohjelmoijan taito ja masiinan suorituskyky.
"Eli onko menetelmää analyyttiseen jakauman selvittämiseen (approksimaatiokin kelpaa, eli jos keskeinen raja-lause on käyttökelpoinen niin..)."
Niin, olikos se niin, että quick sortille tyypillinen aika on O(n* log(n)), mutta jos sille tyrkkää ilkeästi jo järjestetyn aineiston niin aika onkin O(n*n) :-; No nyt sitten joku haluaa tietää, miten vino lajitteluoperaatioiden lukumäärien jakauma on.
Suosittelen Monte Carloa eli heität vaan "satunnaista" aineistoa "riittävän" monta kertaa lajiteltavaksi ja mittaat, montako kertaa vertailuoperaatio piti suorittaa. Mitattu jakauma lähenee sitä todellista jakaumaa otoksen kasvaessa. Tosin jos menetelmällä on joku heikko kohta, anomalia, kuten quick sortilla, niin se ei välttämättä tule esille pienellä testillä. Tai jos menetelmä käyttäytyy hyvin suurella aineistolla täysin eri tavalla, niin sekään ei tule esille.
Sitten sinun täytyy vielä päättää, mistä jakaumasta se lajittelualgoritmille syötettävä satunnainen aineisto tulee. Satunnaisluvuilla mittaamista voi tehostaa toisinaan quasisatunnaisluvuilla.
Jos tutkittava algoritmi on kovin kinkkinen niin saatat joutua tarkistamaan tulokset eri satunnaislukugeneraattoreilla.