GLOBAL KNOWLEDGE ARK

Žinynas

Žinių pagrindai

Tyrinėkite sąvokas, dėsnius, lygtis ir metodus, jų taikymą ir šaltinius. Pasirinkite pažinimo sritį arba raskite konkretų žinyno įrašą.

Daugiau filtrų

Žinyno įrašai

Rodoma įrašų: 31–60 iš 1709

Fizika · MatavimasCezio-133 apibrėžiamasis dažnis

ΔνCs žymi netrikdomo cezio-133 atomo pagrindinės būsenos hipersmulkiosios sandaros šuolio dažnį. Jo skaitinė vertė SI vienetais yra tiksliai fiksuota.

ApibrėžimasMatematika ir logika · InformacijaKlasikiniai teiginiai ir loginės jungtys

Klasikinė logika jungia tiesos vertes turinčius teiginius apibrėžtomis loginėmis jungtimis.

ApibrėžimasMatematika ir logikaAksiomos, dedukcija ir matematinis įrodymas

Matematiniu įrodymu išvada išvedama remiantis nurodytomis prielaidomis ir taisyklėmis.

MetodasMatematika ir logika · InformacijaAibės, priklausymas ir pagrindinės operacijos

Aibė nusako elementų priklausymą, neatsižvelgiant į pakartotinį tų pačių elementų išvardijimą.

ApibrėžimasMatematika ir logika · InformacijaFunkcijos, apibrėžimo sritis ir kodomenas

Funkcija kiekvienam savo apibrėžimo srities elementui priskiria lygiai vieną reikšmę.

ApibrėžimasMatematika ir logika · InformacijaMatematinė indukcija

Indukcijos bazė ir bendrasis indukcijos žingsnis leidžia įrodyti, kad predikatas teisingas visiems neneigiamiems sveikiesiems skaičiams.

MetodasMatematika ir logika · MatavimasEuklidiniai statieji trikampiai ir Pitagoro teorema

Euklidinio stačiojo trikampio statinių ilgių kvadratų suma lygi įžambinės ilgio kvadratui.

Matematinis teiginysMatematika ir logika · FizikaSinusas, kosinusas ir vienetinis apskritimas

Sinusas ir kosinusas yra vienetinio apskritimo taško koordinatės, kurių kvadratų suma lygi vienetui.

Matematinis teiginysMatematika ir logika · InformacijaKompleksiniai skaičiai

Kompleksinis skaičius turi realiąsias koordinates a ir b bei menamąjį vienetą, tenkinantį lygybę i²=−1.

ApibrėžimasMatematika ir logika · Informacija · FizikaTiesiniai atvaizdžiai ir jų matricinis vaizdavimas

Tiesinis atvaizdis išsaugo tiesinius darinius ir, pasirinkus bazes, turi matricą.

ApibrėžimasMatematika ir logikaRealiųjų reikšmių funkcijos riba

Baigtinė riba leidžia kontroliuoti funkcijos reikšmės paklaidą, kai argumento atstumas yra pakankamai mažas.

ApibrėžimasMatematika ir logika · FizikaIšvestinė taške

Išvestinė yra baigtinė vietinių skirtuminių santykių riba.

ApibrėžimasMatematika ir logika · FizikaApibrėžtinis integralas ir kaupimas su ženklu

Apibrėžtinis integralas yra mažų įnašų kaupimo su ženklu ribinė vertė.

ApibrėžimasMatematika ir logika · FizikaPagrindinė matematinės analizės teorema

Tolydumas susieja diferencijavimą ir integravimą.

Matematinis teiginysMatematika ir logika · InformacijaTikimybinė erdvė ir aksiomos

Tikimybė įvykiams priskiria neneigiamus, normuotus svorius; poromis nesutaikomų įvykių skaičiosios sąjungos svoris yra tų įvykių svorių suma.

ApibrėžimasMatematika ir logika · InformacijaSąlyginė tikimybė ir nepriklausomumas

Sąlygojant apsiribojama teigiamos tikimybės įvykiu.

ApibrėžimasMatematika ir logika · InformacijaDiskrečiojo atsitiktinio dydžio matematinė viltis

Matematinė viltis – tai galimų reikšmių suma, kurioje kiekvienos reikšmės svoris yra jos tikimybė.

ApibrėžimasMatematika ir logika · MatavimasPopuliacijos vidurkio pasikliautinasis intervalas

Pasikliovimo lygmuo nusako, kokia dalis pakartotinai sudaromų imčių intervalų, gautų taikant intervalų sudarymo procedūrą, apima parametrą.

MetodasInformacija · Matematika ir logikaBitai ir dvejetainis kodavimas be ženklo

Bitas turi dvi galimas būsenas; fiksuoto ilgio dvejetainis žodis be ženklo koduoja sveikąjį skaičių.

ApibrėžimasInformacija · Matematika ir logikaDiskrečiojo skirstinio Šenono entropija

Šenono entropija matuoja neapibrėžtį nurodytame tikimybių skirstinyje.

ApibrėžimasInformacijaAlgoritmas ir sprendimo procedūra

Algoritmas nusako efektyviai įvykdomus žingsnius; sprendimo procedūra turi baigti darbą su kiekviena leistina įvestimi.

MetodasInformacija · Matematika ir logikaSustojimo problemos neišsprendžiamumas

Bendrajame skaičiavimo modelyje nėra visur apibrėžto algoritmo, kuris nustatytų, ar programa sustos, kiekvienai programai ir įvesčiai.

Matematinis teiginysInformacija · Matematika ir logikaAsimptotiniai 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.

ApibrėžimasMatavimasPagrindiniai SI vienetai

Septyni pavadinimus turintys pagrindiniai vienetai sudaro SI dydžių sistemos pagrindą.

ApibrėžimasMatavimasSI dešimtainiai priešdėliai

Priešdėlių simboliai nurodo dešimtainius mastelio daugiklius.

ApibrėžimasMatavimasMetrologinė sietis

Susieti rezultatą su atskaitos pagrindu per dokumentuotus kalibravimus.

ApibrėžimasMatavimas · Matematika ir logikaPirmosios eilės neapibrėžties sklidimas

Sujungti įėjimo dydžių neapibrėžtis taikant matavimo modelį.

MetodasMatavimas · Fizika · Matematika ir logikaDimensijų suderinamumas

Naudokite dimensijas neįmanomoms fizikinių dydžių lygtims aptikti.

MetodasFizika · Žemė ir kosmosasNiutono gravitacija

Taškinių masių trauką modeliuoja jėga, atvirkščiai proporcinga atstumo kvadratui.

ModelisFizikaDažnis, bangos ilgis ir fazinis greitis

Susieti periodinės bangos pasikartojimą erdvėje ir laike.

Apibrėžimas
ApibrėžimasPatikrinta pagal šaltinius

Asimptotiniai viršutiniai rėžiai ir didysis O

InformacijaMatematika ir logika

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.

  1. National Institute of Standards and Technology (NIST)4 šaltiniai
    1. Dictionary of Algorithms and Data Structures: Big-O notationPaul E. Black / US National Institute of Standards and TechnologyŽinynasxlinux.nist.govSkaityti šaltinį
    2. Dictionary of Algorithms and Data Structures: Worst caseUS National Institute of Standards and TechnologyŽinynasxlinux.nist.govSkaityti šaltinį
    3. Dictionary of Algorithms and Data Structures: Average caseUS National Institute of Standards and TechnologyŽinynasxlinux.nist.govSkaityti šaltinį
    4. Dictionary of Algorithms and Data Structures: Amortized costUS National Institute of Standards and TechnologyŽinynasxlinux.nist.govSkaityti šaltinį
  2. Data Structures and Algorithms · IntroductionUniversity of HelsinkiMokomoji medžiagatira.mooc.fiSkaityti šaltinį

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.

Susiję žinyno įrašai

Tyrinėkite ryšius šioje pažinimo srityje ir jos sąsajas su kitomis sritimis.

Rodomi 1–8 iš 8 ryšių

Mokslinių žinių ryšiai · 8 / 8

Ryšio tipas nusako santykį. Susieti teiginiai, šaltiniai ir sąlygos apibrėžia jo taikymo ribas.

  1. Remiasi apibrėžimu
    Ryšio šaltiniai · 1

    Susieti teiginiai

    • 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į.
  2. Remiasi apibrėžimu
    Ryšio šaltiniai · 1

    Susieti teiginiai

    • 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.
  3. Remiasi apibrėžimu
    Ryšio šaltiniai · 1

    Susieti teiginiai

    • 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ą.
  4. Remiasi apibrėžimu
    Ryšio šaltiniai · 1

    Susieti teiginiai

    • 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).
  5. Remiasi apibrėžimu
    Ryšio šaltiniai · 1

    Susieti teiginiai

    • 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.
  6. Remiasi apibrėžimu
    Ryšio šaltiniai · 1

    Susieti teiginiai

    • 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.
  7. Remiasi apibrėžimu
    Ryšio šaltiniai · 1

    Susieti teiginiai

    • 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).
  8. Remiasi apibrėžimu
    Ryšio šaltiniai · 1

    Susieti teiginiai

    • 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).
Įrašo informacijaNuolatinė nuoroda į šį įrašą ↗
Įrašo identifikatorius
info-asymptotic-complexity
Versija
core.1
Struktūruotas žinyno įrašas
Esminiai pagrindai · pirmasis rinkinys