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
743
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
Aivosyöpää sairastava Olga Temonen TV:ssä - Viimeinen Perjantai-keskusteluohjelma ulos
Näyttelijä-yrittäjä Olga Temonen sairastaa neljännen asteen glioomaa eli aivosyöpää, jota ei ole mahdollista leikata. Hä802809Pelotelkaa niin paljon kuin sielu sietää.
Mutta ei mene perille asti. Miksi Venäjä hyökkäisi Suomeen? No, tottahan se tietenkin on jos Suomi joka ei ole edes soda2951626Mikä saa ihmisen tekemään tällaista?
Onko se huomatuksi tulemisen tarve tosiaan niin iso tarve, että nuoruuttaan ja tietämättömyyttään pilataan loppuelämä?2461527- 871371
IL - VARUSMIEHIÄ lähetetään jatkossa NATO-tehtäviin ulkomaille!
Suomen puolustuksen uudet linjaukset: Varusmiehiä suunnitellaan Nato-tehtäviin Puolustusministeri Antti Häkkänen esittel4011349Nyt kun Pride on ohi 3.0
Edelliset kaksi ketjua tuli täyteen. Pidetään siis edelleen tämä asia esillä. Raamattu opettaa johdonmukaisesti, että3961273Esko Eerikäinen tatuoi kasvoihinsa rakkaan nimen - Kärkäs kommentti "Ritvasta" lävähti somessa
Ohhoh! Esko Eerikäinen on ottanut uuden tatuoinnin. Kyseessä ei ole mikä tahansa kuva minne tahansa, vaan Eerikäisen tat381027Kiitos nainen
Kuitenkin. Olet sitten ajanmerkkinä. Tuskin enää sinua näen ja huomasitko, että olit siinä viimeisen kerran samassa paik2999Hyväksytkö sinä sen että päättäjämme ei rakenna rauhaa Venäjän kanssa?
Vielä kun sota ehkäpä voitaisiin välttää rauhanponnisteluilla niin millä verukkeella voidaan sanoa että on hyvä asia kun329854Miksi Purra-graffiti ei nyt olekkaan naisvihaa?
"Pohtikaapa reaktiota, jos vastaava graffiti olisi tehty Sanna Marinista", kysyy Tere Sammallahti. Helsingin Suvilahden254832