Laikas, atmintis ir užkoduotos įvesties dydis
Deterministinio sprendimo algoritmo laiko sąnaudos matuojamos žingsnių skaičiumi, o atminties sąnaudos – naudojamų atminties langelių skaičiumi; blogiausio atvejo ribos nustatomos imant maksimumą tarp vienodo užkoduoto ilgio įvesčių.
Esminės žinios
Deterministinio sprendimo algoritmo laiko sąnaudos matuojamos žingsnių skaičiumi, o atminties sąnaudos – naudojamų atminties langelių skaičiumi; blogiausio atvejo ribos nustatomos imant maksimumą tarp vienodo užkoduoto ilgio įvesčių. Mašinos modelis ir kodavimas yra teiginio dalis: skaičiaus dydis nėra tas pats, kas jo dvejetainio užrašo ilgis.
Sąlygos ir taikymo ribos
- Nurodant atminties sąnaudų ribą, reikia patikslinti, ar įskaičiuojama įvesčiai saugoti naudojama atmintis.
- Polinominis laikas tebėra matematinė klasė, o ne praktinės spartos garantija kiekvienam polinomo laipsniui.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitos 12 skaidrės 2, 6, 20–24 ir 33: išteklių apibrėžtys, blogiausias atvejis pagal įvesties ilgį ir modelio bei praktinio įgyvendinamumo ribos.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaitytas visas 241 glaustas teiginys, hipotezės, atskirai pateiktos lygtys ir susitarimai bei visos 596 iš šių įrašų išeinančios semantinės sąsajos; peržiūrėta visa autoriaus 241 įrašo tikslių šaltinių patikros matrica ir nurodyti ribotumai. Siekiant aprėpti visą rinkinį, perskaityti 105 ankstesni faktiškai perimti matematikos ir informacijos įrašai. Nepriklausomai tikslingai peržiūrėti pirminių šaltinių skyriai išvardyti toliau; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atliekama informacinio turinio peržiūra, o ne žmogaus specialisto patvirtinimas, išsamus vadovėlio atkūrimas ar eksperimentinis atkartojimas. Peržiūros patvirtinimas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-time-space-cost-model
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra