Ero sivun ”Asymptoottinen suoritusaika” versioiden välillä
| [katsottu versio] | [katsottu versio] |
Poistettu sisältö Lisätty sisältö
Ei muokkausyhteenvetoa |
Ei muokkausyhteenvetoa |
||
Rivi 5:
[[Aikavaatimus|Aikavaatimuksen]] lisäksi algoritmilla voi olla [[tilavaatimus]] eli paljonko resursseja (muistia) suoritus voi käyttää.
== Taustaa ==
J. Hartmanis ja R. E. Stearns kirjoittivat vuonna 1965 artikkelin ''On The Computational Complexity of Algorithms'', jossa laskennallista ([[komputaatio]]) kompleksisuutta verrattiin miten nopeasti kuvitteellinen [[Turingin kone]] pystyy käsittelemään käskynauhaa. Abstraktia mallia käytettiin, koska kaikki digitaaliset tietokoneet ovat ideaalisessa muodossa Turingin koneen kaltaisia.<ref>{{Verkkoviite | osoite = https://www.ams.org/journals/tran/1965-117-00/S0002-9947-1965-0170805-7/S0002-9947-1965-0170805-7.pdf | nimeke = On The Computational Complexity of Algorithms | tekijä = J. Hartmanis & R. E. Stearns | tiedostomuoto = PDF | viitattu = 12.7.2022 | kieli = {{en}} }}</ref>
== Merkintätavat ==
| |||