Ero sivun ”Asymptoottinen suoritusaika” versioiden välillä
| [katsottu versio] | [katsottu versio] |
Poistettu sisältö Lisätty sisältö
erillinen tapaus |
Ei muokkausyhteenvetoa |
||
Rivi 4:
Puhtaan [[matematiikka|matematiikan]] ja mekaanisen laskennan välillä on useita eroja, joista yksi on monien matematiikan [[funktio]]iden [[asymptootti]]nen luonne. Mikäli näitä funktioita pyritään ratkaisemaan [[alkeisoperaatio]]iden avulla, laskenta-aika venyy. [[Pii (vakio)|Piin]] desimaalien laskenta on tästä yksi esimerkki. Käytännössä usein riittää kuvata yhtälö yksinkertaisemmassa muodossa, koska käsiteltävien [[desimaali]]en määrä monissa järjestelmissä (esimerkiksi talous-) on rajoitettu. Alla on matemaattinen kuvaus riittävällä tarkkuudella ratkeavasta funktiosta.
[[Aikavaatimus|Aikavaatimuksen]] lisäksi algoritmilla voi olla [[tilavaatimus]] eli paljonko resursseja (muistia) suoritus voi käyttää.
== Merkintätavat ==
Rivi 63:
Samalla periaatteella voidaan todistaa, että 12n<sup>7</sup> = ''Ο''(n<sup>8</sup>) on tosi.{{Lähde|6. maaliskuuta 2012|Tuskinpa vain}}
== Kirjallisuutta ==
* Sanjeev Arora & Boaz Barak: ''Computational Complexity: A Modern Approach'', [https://theory.cs.princeton.edu/complexity/book.pdf Draft] (PDF) {{en}}
[[Luokka:Tietojenkäsittelytiede]]
| |||