Paljonko on seuraavanlaisen algoritmin aikavaativuus?
Lisää listaan
Poista listasta
Molempien aikavaatimus on erään listauksen mukaan O(1), mutta mitä se on yhteensä tuolta pätkältä???
Tietääks kukaan mitään näistä?
algoritmin aikavaativuus?
tyhmä
13
854
Vastaukset
- Punikki & 7 hyypiötä
Yhteensä O(1) eli vakioajan, mikä se sitten onkaan. Yhden alkion lisääminen listaan vie tietyn ajan aina. Samoin sen poisto. Siksi O(1). Molemmat peräkkäin vievät edelleen vakioajan joka kerta eli O(1). Tämä siksi että aina pelataan 1 listan alkion kanssa. Edelleen N:n alkion lisääminen/poistaminen vie ajan O(N). Ajalla tässä on vain sen verran tekemistä, että tuo O() kertoo, miten "nopeasti" algoritmin suoritus pahimmassa tapauksessa kestää. Jos 1 alkion lisäys kestää 1,2 sekuntia, niin 2 alkion lisäys vie 2,4 sekuntia jne. Eli N:n alkion lisäys/poisto kestää O(N) eli aikakompleksisuus kasvaa lineaarisesti eli suoraan suhteessa käsiteltävien alkioiden lukumäärään.
- Piru
Prosessorien manuaaaleista noi löytyy, kaippa c:stäkin jne. vaikka yleensä korkeamman tason ohjelmointikielillä noita aikoja mietitään aika harvoin. Jossei sitten tehdä jotain sulautettua järjestelmää. Eli konekielikäskyn suorittaminen kestää tietyn määrän kellojaksoja joka ajallisesti riippuu sitten prossan kellotaajuudesta.
- tyhmä
Piru kirjoitti:
Prosessorien manuaaaleista noi löytyy, kaippa c:stäkin jne. vaikka yleensä korkeamman tason ohjelmointikielillä noita aikoja mietitään aika harvoin. Jossei sitten tehdä jotain sulautettua järjestelmää. Eli konekielikäskyn suorittaminen kestää tietyn määrän kellojaksoja joka ajallisesti riippuu sitten prossan kellotaajuudesta.
juu, mut meillä tarkotetaan ihan vain algoritmillisesti tuota aikavaatimusta.
Eli ei otetan huomioon mitään kellotaajuuksia tms.
Eli yritetäänpä siis vertailla eri algoritmeja toisiinsa ja ehkäpä saada selville että mikä onkaan paras. - tyhmä
Kiitos, juuri tuota tarkoitin!
Elikkäs mun ei siitä tarviikaan tietää muuta kuin tuo O(1). En osannut odottaa sen olevan noin yksinkertaista (tuossa tapauksessa).
Eri asiahan on sitten kun alan laskemaan aikavaatimusta algoritmille jossa on just erilaisia eli O(1) ja O(n) ja vaikka mitä (jos tutkii osissa), jolloin taas oon pulassa. No, jospa se tästä! - Punikki & 7 hyypiötä
Piru kirjoitti:
Prosessorien manuaaaleista noi löytyy, kaippa c:stäkin jne. vaikka yleensä korkeamman tason ohjelmointikielillä noita aikoja mietitään aika harvoin. Jossei sitten tehdä jotain sulautettua järjestelmää. Eli konekielikäskyn suorittaminen kestää tietyn määrän kellojaksoja joka ajallisesti riippuu sitten prossan kellotaajuudesta.
itse asiassa ohjelmointikielellä ja alustalla ei ole mitään tekemistä aikakompleksisuustarkastelun kanssa. Kieli voi olla assembly tai basic, kompleksisuus on silti sama. Algoritmin suorittamiseen ei välttämättä edes tarvita tietokonetta ja em. tarkastelu pätee silti esim. erilaisissa lajittelumenetelmissä. Kuplalajittelu on O(n^2), kekolajittelu O(n lg n) tehtiinpä lajittelu koneella tai ilman. Pienillä n:n arvoilla ero tuskin tietokoneella tuntuu, mutta n:n ollessa tarpeeksi suuri alkaa aikaerot tuntumaan. Konekielikäskyjen vaatimat kellojaksot ovat eri asia, jotka toki vaikuttavat joskus hyvinkin paljon ohjelman suoritukseen.
- Punikki & 7 hyypiötä
tyhmä kirjoitti:
Kiitos, juuri tuota tarkoitin!
Elikkäs mun ei siitä tarviikaan tietää muuta kuin tuo O(1). En osannut odottaa sen olevan noin yksinkertaista (tuossa tapauksessa).
Eri asiahan on sitten kun alan laskemaan aikavaatimusta algoritmille jossa on just erilaisia eli O(1) ja O(n) ja vaikka mitä (jos tutkii osissa), jolloin taas oon pulassa. No, jospa se tästä!Hyvä että helpotti. Jos algoritmit kiinnostaa, kannattaa tutustua seur. opukseen:
Introduction to Algorithms
Cormen, Leiserson, Rivest
The MIT Press Punikki & 7 hyypiötä kirjoitti:
Hyvä että helpotti. Jos algoritmit kiinnostaa, kannattaa tutustua seur. opukseen:
Introduction to Algorithms
Cormen, Leiserson, Rivest
The MIT PressVanha viesti, mutta varoituksen sana on paikallaan. "Introduction to Algorithms" opettaa algoritmien aikavaativukset väärin, ja ainakaan minun lähettämä korjausehdotus ei mennyt läpi. Periaatteessa kirjan opeilla pärjää käytännössä, mutta se ei ole matemaattisesti korrekti tapa tehdä asioita. Jos haluaa opetella asiat täsmällisesti, niin kannattaa opetella O-notaatio sivulta http://www.artofproblemsolving.com/Forum/viewtopic.php?f=296&t=31517&start=20 .
- tyhmä
vielä kysymys!
Mikäs on ALGORITMIN tilavaativuus??? Miten sen voi päätellä?- ?
Listan muistin tarve:
Alkion vaatima muisti x alkioiden määrä
algoritmin muistin tarve:
Pino ja lisäksi mahdolliset apu taulukot yms muut jos käytössä.
- tyhmä
Apua, en vieläään ymmärrä!
- orkaborka
Riippuu toteutuksesta ja kaikilla toteutuksilla on omat hyvät ja huonot puolensa. Esim. linkitetyssä listassa alkioiden lisääminen keskelle tai poistaminen keskeltä on nopeaa, mutta taas tiettyjen alkioiden etsiminen on hidasta, koska alkioita täytyy selata yksi kerrallaan.
http://en.wikipedia.org/wiki/Linked_list- tyhmä
mikä on alkio?
- gggggggggggfffdfdd
tyhmä kirjoitti:
mikä on alkio?
Yksi listan elementti, solmu, alkio..
http://fi.wikipedia.org/wiki/Linkitetty_lista
Perinteisessä listassa tiedot tallentuvat peräkkäisiin muistipaikkoihin. Linkitetyssä listassa näin ei ole vaan jokainen alkio osoittaa missä seuraava alkio on.
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Purra hyökkää nyt suomalaisen duunarin kimppuun teettämällä mamuilla palkatonta työtä
Niinpä niin. Persut duunaripuolue, HAH. Joko alkaa kovapäisinkin persu älyämään, että persut ovat Suomen kansan vastain36712340Purra ehdottaa vaan Tanskan mallia, joka on erittäin hyvä malli
Purra ehdotti helmikuussa Suomeen Tanskan mallia, jossa maahanmuuttajilta vaaditaan työntekoa sosiaalitukien saamiseksi.2555397Kokoomusnuoret: Sosiaalitukien työvelvoitteen tulisi koskea kaikkia
Riikka Purra on esittänyt, että maahanmuuttajilta tulisi edellyttää palkatonta työtä sosiaalitukien vastineeksi. Kokoom2143932Purra vaatii: Työvelvoite maahanmuuttajille ja kantasuomalaisille pitkäaikaistyöttömille
Jos Perussuomalaiset ja Kokoomus ovat seuraavan hallituksen kaksi johtavaa puoluetta, on suomalaisille pitkäaikaistyöttö1962609Jyrki Linnankivi, Jyrki 69 - Goottirokkarista kirkonmieheksi Lappiin!
Jyrki Linnankivi eli Jyrki 69 on The 69 Eyes -rockyhtyeen vokalisti. Lauluhommien lisäksi hän sanoittaa, säveltää ja sov151982Onnea Maria ja Vilma Amazing Race -voitosta!
Maria Guzenina ja Vilma Vähämaa voittivat Amazing Race Suomi -kisan. Voiton hetkellä Guzenina paljasti, miksi valitsi Vi191824Mikä on mielestäsi paras miestyyppi?
Esimerkit kärjistettyinä: a) perustavallinen/tasainen b) himourheilija c) varakas, turvallinen elättäjä d) puolikrimina167900Martina Aitolehti
Instagramissa pomppas esille Martinan kumipallot. Ihan säikähin. Ja tää on Martina-ketju!271852No kolahtaako kukaan
Samalla tavalla kuin mä? Harmi kun et uskaltanut kohdata. Ehkä me löydetään jotkut muut jotka voi olla konkreettisempiak74772Rippituoli
Kerro joku synkkä tai outo salaisuus, joka liittyy ikävääsi kaivattuasi kohtaan. Tee tunnustus anonyyminä. Se helpottaa59726