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
863
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
Diesel-ammattilainen kehuu Sanna Marinia
"Sanna Marinin (sd) hallitus loi neljä vuotta sitten väliaikaisen polttoainetukijärjestelmän, kun energianhinnat nousi362759Pitkänperjantain kunniaksi tekoälyn analyysi Riikka Purran kirjoituksesta
🧠 Mitä se kertoo "riikka"-nimimerkin lähijunassa tapahtuneesta? 1. Asenteellinen ja epäasiallinen sävy: Kirjoitus purs122549100 prosentin perintövero korjaisi myös Hitas-ongelman
Moni ei uskalla kieltäytyä perinnöstä maineen menettämisen uhalla, joten sitten tulee näitä tilanteita, joissa joutuu es372258Riikan antisakset leikkaavat bensan hintaa ylöspäin
Sannan aikoina bensaa sai 1,3 euron litrahinnalla ja Riikka leikkasi sen euron ylemmäksi reiluun 2 euroon. Joko on saks201861Iso poliisioperaatio Lapualla
Paikalla oli silminnäkijän mukaan myös kolme ambulanssia. https://www.is.fi/kotimaa/art-2000011924650.html Onko virpo371547Olen aika varma
että meidän tiemme risteäminen oli ainutkertainen tapahtuma elämässäni. En tule koskaan kohtaamaan ketään muuta, joka sa511545- 381473
Sukupuolineutraalit liikennemerkit yksi persujen älynväläys
Samassa rytäkässä kaikki syrjäseutujen bussipysäkkien liikennemerkitkin vaihdettiin, vaikkei bussia ole liikennöinyt enä251353- 271178
- 241114