Asimptotiniai viršutiniai rėžiai ir didysis O
Didysis O nusako augimo viršutinį rėžį: nuo tam tikro įvesties dydžio nagrinėjama funkcija neviršija pastoviu daugikliu padaugintos palyginamosios funkcijos.
Esminės žinios
Neneigiamoms sąnaudų funkcijoms T(n)=O(g(n)) reiškia, kad egzistuoja konstantos c>0 ir n₀, tokios, kad T(n)≤cg(n) kiekvienam n≥n₀. Nurodant laiko ar atminties sudėtingumo rėžį, būtina apibrėžti skaičiavimo modelį, įvesties dydžio matą ir analizuojamą atvejį.
Vertės ir lygtys
T(n)=O(g(n)) ⇔ ∃c>0, n₀: 0≤T(n)≤cg(n) for all n≥n₀
- T(n)
- Neneigiamos išteklių sąnaudos, kai įvesties dydis yra n
- g(n)
- Neneigiama palyginimo funkcija
- c
- Fiksuotas teigiamas daugiklis
- n₀
- Fiksuotas slenkstinis įvesties dydis
- n
- Įvesties dydis pagal nurodytą reprezentaciją
Sąlygos ir taikymo ribos
- Konstantos c ir n₀ yra fiksuotos ir nepriklauso nuo n.
- Viršutinis rėžis nebūtinai yra tikslus ir nenurodo faktinės vykdymo trukmės.
- Blogiausio atvejo, vidutinio atvejo ir amortizuotosios sąnaudos yra skirtingi dydžiai.
Šaltiniai · 5
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
National Institute of Standards and Technology (NIST)4 šaltiniai
- Dictionary of Algorithms and Data Structures: Big-O notationPaul E. Black / US National Institute of Standards and TechnologyŽinynas
- Dictionary of Algorithms and Data Structures: Worst caseUS National Institute of Standards and TechnologyŽinynas
- Dictionary of Algorithms and Data Structures: Average caseUS National Institute of Standards and TechnologyŽinynas
- Dictionary of Algorithms and Data Structures: Amortized costUS National Institute of Standards and TechnologyŽinynas
- Data Structures and Algorithms · IntroductionUniversity of HelsinkiMokomoji medžiaga
Pagrindimas ir peržiūra
Didžiojo O apibrėžtis neneigiamoms sąnaudoms ir išteklių poreikio augimo interpretacija.
2026-10-10 · Patikrintos konstantos ir asimptotinio taikymo ribos; neteigiama nieko apie konkrečios realizacijos našumą.
Pagrindinių žinių peržiūra
2026-10-10 · Fresh primary-source inspection of the complete compact record, including every statement, equation, quantity and material condition, followed by independent AI editorial review. This check does not certify all linked lessons or every passage of every cited publication.
Šaltiniai iš kitų vietų
Sutampa nurodytose ribose
Big-O uses fixed constants and an eventual upper bound on operations as input length grows.
An upper bound is not a single-machine wall-clock measurement.
University of Helsinki, Department of Computer Science
- Data Structures and Algorithms · Introduction Finlandanglų
Efficiency of algorithms; Analysis of algorithms
- Data Structures and Algorithms · Introduction
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-asymptotic-complexity
- Versija
- core.1
- Struktūruotas žinyno įrašas
- Esminiai pagrindai · pirmasis rinkinys