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
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
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į.
Klasei P priklauso sprendimo uždaviniai, kuriuos deterministinis algoritmas išsprendžia per laiką, polinominį įvesties ilgio atžvilgiu. Klasei NP priklauso uždaviniai, kurių egzemplioriams su atsakymu „taip“ egzistuoja polinominio dydžio sertifikatai, patikrinami per polinominį laiką, o egzemplioriams su atsakymu „ne“ nėra nė vieno priimamo sertifikato. P⊆NP.
Stekas pašalina vėliausiai pridėtą elementą, o eilė — anksčiausiai pridėtą. Žodynas leidžia ieškoti pagal raktą, įterpti ir šalinti. Masyvai word-RAM modelyje leidžia pasiekti indeksuotą elementą per pastovų laiką, o susietojo sąrašo perėjimas iki savavališko indekso trunka tiesinį laiką.
Rikiuojant n skirtingų raktų dvejetainiais palyginimais, galimos n! išsidėstymo tvarkos. Todėl algoritmo sprendimų medžio gylis blogiausiu atveju turi būti bent ⌈log₂(n!)⌉, o tai yra Ω(n log n).
Teigiamiems sveikiesiems skaičiams a₁,…,aₙ ir tikslinei sumai T≥0 galioja D(i,t)=D(i−1,t) arba [t≥aᵢ ir D(i−1,t−aᵢ)], kai D(0,0)=tiesa, o kitos pradinės būsenos yra klaidingos. Skaičiavimui reikia O(nT) ribotos kainos operacijų su būsenomis; tai pseudopolinominis sudėtingumas, nes T užkoduotas dvejetaine forma.
Surikiuotame masyve su tiesiogine prieiga palyginkite ieškomą reikšmę su viduriniu raktu ir atmeskite tą pusę, kurioje jos negali būti; kartokite, kol rasite atitinkantį raktą arba likęs intervalas bus tuščias. Kiekviename žingsnyje intervale išsaugomi visi galimi atitikmenys, o jo dydis sumažinamas perpus.
Norint gauti didžiausią suderinamų intervalų skaičių, reikia pakartotinai rinktis anksčiausiai pasibaigiantį iš likusių intervalų ir atmesti su juo persidengiančius intervalus. Pakeitus pirmąjį optimalaus sprendinio intervalą šiuo pasirinktu intervalu, galimų likusių intervalų aibė negali sumažėti; tuo grindžiamas įrodymas sukeitimu. Rikiuojant pagal pabaigos laiką, laiko sudėtingumas yra O(n log n).
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).