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
806
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
Tänään pyörit ajatuksissa enemmän, kun erehdyin lukemaan palstaa
En saisi, silti toivon että sinä vielä palaat ja otetaan oikeasti selvää, hioituuko särmät ja sulaudummeko yhteen. Vuod225474- 324810
- 282721
- 342344
- 372058
- 152008
En ole koskaan kokenut
Ennen mitään tällaista rakastumista. Tiedän että kaipaan sinua varmaan loppu elämän. Toivottavasti ei tarvitsisi vain ka191647- 121591
- 231462
Voi ei! Jari Sillanpää heitti keikan Helsingissä - Hämmästyttävä hetki lavalla...
Ex-tangokuningas on parhaillaan konserttikiertueella. Hän esiintyi Savoy teatterissa äitienpäivänä. Sillanpää jakoi kons251429