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
841
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
Nainen kokki autossa kammottavan kuoleman sähköauto-Teslan syttyessä tuleen.
https://www.is.fi/autot/art-2000011652873.html Näin vaarallisia sähköautopalot voivat olla.845157Persuja ei aluevaltuustoissa näy
Ei tunnu persuja paljon paikalliset asiat kiinnostavan, vaan ainoastaan ulkomaalaiset, joku Israel ja Trumpin fanitus.253480Päivän Riikka: Uudenkaupungin autotehdas hiljeni
Näin ne 100 000 uutta pysyvää ei-tempputyötä yksityiselle sektorille tämän hallituksen ansiosta syntyy. Työntekijöille j382828Riikka vie Suomen kohta ykköseksi työttömyyskisassa
Espanja: 10,5 % Suomi: 10,3 % Ruotsi: 9,3 % Kisa on tiukkaa, mutta Riikalla hyvä draivi päällä. Vasemmistolaisen päämin91972Kerro kaivattusi nimi tai nimikirjaimet
🌠 Tähdenlento! Kirjoittamalla kaivattusi nimen tai nimikirjaimet tähän, saattaa toiveesi toteutua.581820- 471586
Alkuvuodesta poistuu työttömyyskorvaus kaikilta joilla on säästössä rahaa
Tippuu korvaukselta iso määrä työttömiä.2631476- 941382
Tämmönen höpsö
Höpönassu mä olen. En mikään erikoinen…hölötän välillä ihan levottomia. Tykkäisit varmasti jos olisin siellä sun vieress441356Hiljaisuus
Tarkoittaa välinpitämättömyyttä, henkistä väkivaltaa ja kiusaamista. Olet valinnut hiljaisuuden.731078