Teta ir apatiniai asimptotiniai rėžiai
Jei sąnaudos f,g yra neneigiamos nuo tam tikro momento, f=Θ(g) reiškia, kad c₁g(n)≤f(n)≤c₂g(n) visiems pakankamai dideliems n, kai konstantos c₁,c₂>0.
Esminės žinios
Jei sąnaudos f,g yra neneigiamos nuo tam tikro momento, f=Θ(g) reiškia, kad c₁g(n)≤f(n)≤c₂g(n) visiems pakankamai dideliems n, kai konstantos c₁,c₂>0. Vien apatinė nelygybė apibrėžia f=Ω(g), o viršutinė – f=O(g).
Sąlygos ir taikymo ribos
- Konstantos nepriklauso nuo n.
- Vieno algoritmo apatinis rėžis nėra savaime kiekvieno tą uždavinį sprendžiančio algoritmo apatinis rėžis.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
NIST formalus dvipusis teta apibrėžimas; atskirai išskleistos viršutinė ir apatinė nelygybės.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi 241 glaustas teiginys, hipotezės, atskirai pateiktos lygtys ir susitarimai bei visos 596 kilmės semantinės nuorodos; peržiūrėta visa autoriaus 241 įrašo tikslių šaltinių patikros matrica ir nurodyti apribojimai. Siekiant aprėpti visą rinkinį, perskaityti 105 ankstesni faktiniai paveldėti matematikos ir informacijos įrašai. Tikslinės nepriklausomai peržiūrėtos pirminių šaltinių dalys išvardytos 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 atliekamas dalykinis sertifikavimas, išsamus vadovėlio atkūrimas ar eksperimentinis atkartojimas. Patvirtinimas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-tight-asymptotic-bounds
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra