On matematiikka , tarkemmin sanottuna analyysi , asymptoottinen vertailu on menetelmä, jonka tutkimiseen kasvuvauhti on funktio on lähellä pisteen tai äärettömään, vertaamalla sitä, että toisen toiminnon pidetään enemmän "Simple". Tämä valitaan usein referenssiasteikolla , joka sisältää yleensä ainakin tiettyjä ns. Perustoimintoja , erityisesti polynomien , eksponentiaalien ja logaritmien summat ja tulot . Vastaavia merkintöjä käytetään erityisesti fysiikassa ja tietojenkäsittelytieteissä , esimerkiksi kuvaamaan tiettyjen algoritmien monimutkaisuutta . Niitä käytetään myös analyyttisessä lukuteoriassa, jotta voidaan arvioida tarkasti virhe, joka on tehty korvaamalla epäsäännöllinen funktio, kuten alkulukujen laskeminen , valitun asteikon funktiolla.
Menetelmä otettiin käyttöön Paul du Bois-Reymondin teoksessa vuodelta 1872; Laskelmien ja tulosten esittämisen helpottamiseksi on kehitetty erilaisia merkintöjä , erityisesti Bachmann (1894), Landau (1909), Hardy (1910), Hardy ja Littlewood (1914 ja 1916) ja Vinogradov ( n. 1930).
Olkoon f ja g kaavojen määrittelemät todelliset funktiot
Tutkimalla kahta toimintoa tiedämme, että g ottaa arvot niin suuria kuin haluamme äärettömyyden läheisyydessä, kun taas f voi ottaa arvot vain välillä 1 ja 3. Osamäärä g jaettuna f au: n äärettömyyden naapurustolla kasvaa jatkuvasti eikä sitä ole rajoitettu. Tässä yhteydessä voimme sanoa, että f on merkityksetön g : n edessä tai että g on hallitseva f : n edessä , äärettömyyden naapurustossa, kirjoitamme (Landau-merkinnät):
tai (Hardyn merkinnät, vanhentuneet)
Hardy-notaatio antaa mahdollisuuden ketjuttaa ylivallan suhteet, esimerkiksi:
Muodollinen määritelmä, kun funktio g ei häviäTämän ominaisuuden virallisesti määrittelemiseksi otetaan huomioon osamäärän käyttäytyminen .
On
Olkoon f ja g todellisen muuttujan x kaksi funktiota . Oletamme, että g ei häviä yli naapurustossa . Me sanomme, että f on vähäinen edessä g , tai että g on hallitseva vuonna edessä f vuonna , ja toteamme , kun
Jos asiayhteys on selkeä, ei määritetä opintoalaa ja muistiinpanot :, jopa . Kuitenkin merkintätapa liittyy aina paikka ja naapurustossa tässä paikassa on merkityksetön on paikallinen käsite .
Tässä Landau-merkinnässä (joskus myös ) symboli lukee pienen o . Hardyn vastaava merkintä on . Nykyään käytämme yksinomaan Landau-merkintää.
OminaisuudetBy kielen väärinkäyttöä, yksi suorittaa ”toimintaa” on ”pieni O” , eli merkityksettömät niistä. Voimme todellakin sanoa, että:
Joko .
Olkoon f ja g todellisen muuttujan x kaksi funktiota . Oletamme, että g ei häviä yli naapurustossa . Me sanomme, että f vastaa g vuonna tai että g on sama kuin f vuonna , ja merkitään
, milloin .Esimerkki
Landaun suuri O-merkintä tarkoittaa yhden funktion hallitsevaa luonnetta toiseen nähden.
Yleensä, kuten Paul Bachmann, joka esitteli tämän symbolin vuonna 1894, käytämme isoa O- kirjainta (saksalaisesta Ordnungista , "järjestys"). Se oli paljon myöhemmin (1976), analogisesti pääoman omega symboli Ω (katso jäljempänä), että Donald Knuth ehdotettu nimetä symboli O nimi pääoman omicron kirjain, joista jälkimmäinen harvoin piirretään siten. Selkeästi eroaa O. Molemmissa tapauksissa käytetty symboli eroaa symbolista 0 (nolla)
Virallinen määritelmäOlkoon f ja g todellisen muuttujan x kaksi funktiota . Sanomme, että F hallitsee g vuonna + ∞ , tai että g dominoi f in + ∞ , ja merkitään (Bachmann merkintää, 1894 tai Landau, 1909)
tai (Hardyn merkintätapa, 1910, vanhentunut)
tai uudestaan (Vinogradov-nootit, 1930-luku)
kun on vakioita N ja C sellaisia
Intuitiivisesti tämä tarkoittaa, että f ei kasva nopeammin kuin g .
Samoin, jos a on reaaliluku, kirjoitamme
jos vakioita d > 0 ja C ovat sellaisia, että
EsimerkkejäVuonna 1914 Hardy ja Littlewood esittivät uuden symbolin Ω, joka määritettiin seuraavasti:
.Funktioiden f ja g oletetaan olevan määriteltyjä ja g- positiivisia äärettömän läheisyydessä. Samoin on kielteinen .
Vuonna 1916 samat kirjoittajat esittivät kaksi uutta symbolia Ω R ja Ω L , jotka määriteltiin seuraavasti:
; .Kuten aiemmin, funktioiden f ja g oletetaan olevan määriteltyjä ja g- positiivisia äärettömän naapurustossa. Joten, on kielteinen ja kielteinen .
Toisin kuin DE Knuth myöhemmin väittää , Edmund Landau käytti myös näitä kolmea symbolia vuonna 1924.
Nämä Hardy- ja Littlewood-merkinnät ovat prototyyppejä, joita Landaun jälkeen ei ilmeisesti ole koskaan käytetty sellaisenaan: Ω R: stä on tullut Ω + ja Ω L: stä Ω - .
Näitä kolmea symbolia käytetään nyt yleisesti analyyttisessä lukuteoriassa samoin kuin osoittamaan, että ehdot ja molemmat täyttyvät.
On selvää, että kukin näistä määritelmistä voimme korvata ∞ mukaan -∞ tai reaaliluku.
Meillä on
ja tarkemmin sanottuna
Meillä on
ja tarkemmin sanottuna
kuitenkin,
On tärkeää korostaa, että kirjoittaminen
on kaksi yhteensopimatonta matematiikan määritelmää, molemmat hyvin yleisiä, toinen analyyttisessä lukuteoriassa , jonka olemme juuri esittäneet, toinen teoriassa algoritmien monimutkaisuudesta . Kun nämä kaksi tieteenalaa kohtaavat, tämä tilanne aiheuttaa todennäköisesti suurta hämmennystä.
Vuonna 1976 Knuth julkaisi artikkelin, jonka päätarkoitus oli perustella saman symbolin Ω käyttö kuvaamaan muuta ominaisuutta kuin Hardyn ja Littlewoodin kuvaama ominaisuus. Hän yrittää vakuuttaa lukijan siitä, että Hardyn ja Littlewoodin määritelmää tuskin koskaan käytetään (mikä on jo vuonna 1976 ollut väärin jo 25 vuoden ajan). Hän väittää, että Landau ei koskaan käyttänyt sitä (mikä on myös väärä). Hän tuntee ehdottomasti tarpeen uudelle käsitteelle ( " Kaikkien tähän mennessä tietojenkäsittelyssä nähtyjen sovellusten kohdalla tiukempi vaatimus […] on paljon sopivampi " ) ja päätti, että Ω-symbolin käyttö on varattava kuvaamaan se. Hän on voimakkaasti järkyttynyt vanhasta määritelmästä ( " Valitettavasti Hardy ja Littlewood eivät määritelleet Ω ( f ( n )) niin kuin halusin " ).
Siksi hän ottaa sekaannuksen riskin ja määrittelee
.Matematiikassa on usein tärkeää pitää silmällä likiarvon virhetermiä. Tätä merkintää käytetään erityisesti, kun käsitellään rajoitettua kehitystä ja vastaavuuslaskelmia. Esimerkiksi eksponenttifunktion laajentaminen järjestykseen 2 voidaan myös kirjoittaa:
ilmaisemaan tosiasian, että virhe, ero , on merkityksetön edessä, kun se pyrkii kohti nollaa.
On huomattava, että tämän tyyppisessä kirjoituksessa operandien lukumäärä on rajoitettava vakiona, joka ei ole riippuvainen muuttujasta: esimerkiksi väite on ilmeisesti väärä, jos ellipsi piilottaa useita termejä, joita ei ole rajoitettu, kun x vaihtelee.
Tässä on luettelo analyysissä yleisesti käytettyjen toimintojen luokista. Muuttuja (merkitty tässä n ) pyrkii + ∞: iin ja c on mielivaltainen todellinen vakio. Kun c on vakio, joka on suurempi kuin 1, toiminnot näkyvät tässä luettelossa kasvavassa suuruusjärjestyksessä.
luokitus | enintään | |
O (1) | moduuli kasvoi vakiona | |
O (loki ( n )) | logaritminen | |
O ((log ( n )) c ) | ( polylogaritminen, jos c on positiivinen kokonaisluku) | |
O ( n ) | lineaarinen | |
O ( n log ( n )) | joskus kutsutaan " lineaariseksi " | |
O ( n log c (n) ) | joskus kutsutaan " lähes lineaariseksi " | |
O ( n 2 ) | neliöllinen | |
Y ( n c ) | ( polynomi, jos c on positiivinen kokonaisluku) | |
O ( c n ) | ( eksponentiaalinen, jos c on positiivinen, joskus " geometrinen ") | |
O ( n! ) | tekijä |
O ( n c ) ja O ( c n ) ovat hyvin erilaisia. Jälkimmäinen sallii paljon nopeamman kasvun, ja tämä kaikille vakioille c > 1. Funktion, joka kasvaa nopeammin kuin mikään polynomi, sanotaan olevan superpolynomi . Toiminnon, joka kasvaa hitaammin kuin mikään eksponentiaalinen, sanotaan olevan subeksponentiaalinen . On sekä superpolynomi- että subeksponentiaalisia funktioita, kuten n log ( n ) -funktio .
Huomaa myös, että O (log n ) on täsmälleen sama kuin O (log ( n c )), koska nämä kaksi logaritmit ovat moninkertainen toisiinsa vakio tekijä ja että merkintä suuri O ”ohituksesi” multiplikatiivinen vakioita . Samoin eri vakiopohjien logaritmit ovat samanarvoisia.
Edellä mainittu luettelo on hyödyllinen, koska on seuraava ominaisuus: jos funktio f on summa toimintoja , ja jos yksi toimintojen summa kasvaa nopeammin kuin muut, niin se määrittää järjestyksen, jossa kasvua f ( n ).
Esimerkki:
jos f ( n ) = 10 log ( n ) + 5 (log ( n )) 3 + 7 n + 3 n 2 + 6 n 3 ,Tätä merkintää voidaan käyttää myös useiden muuttujien toimintojen kanssa:
Kirjoittaminen: | kun |
vastaa ehdotusta: |
Joillekin tämä merkintätapa väärinkäyttää tasa-arvon symbolia , koska se näyttää rikkovan tasa-arvon aksiomia : "samanlaiset asiat ovat yhtä suuria toistensa kanssa" (toisin sanoen tämän merkinnän avulla tasa-arvo n 'on enemmän vastaavuus) suhde ). Mutta voimme myös ottaa sen huomioon kirjoituksessa
merkintä "= O" tarkoittaa yhtä operaattoria, jonka kirjoituksessa merkillä "=" ei ole omaa itsenäistä olemassaoloa (ja erityisesti se ei tarkoita vastaavuussuhdetta). Tässä tapauksessa luokitusta ei enää väärinkäytetä, mutta silti sekaannusvaara. On myös mahdollista määritellä O ( g ( x )) joukoksi toimintoja, joiden elementit ovat kaikki funktioita, jotka eivät kasva nopeammin kuin g , ja käyttää joukko-merkintöjä osoittamaan, onko tietty funktio joukon elementti määritelty. Esimerkiksi :
Molempia sopimuksia käytetään yleisesti, mutta ensimmäinen (ja vanhin) on XXI - luvun alkuun saakka. Tämän ongelman välttämiseksi käytämme (aivan yhtä yleisesti) Vinogradov-merkintää (katso alla).
Toinen ongelma on, että on tarpeen ilmoittaa selvästi muuttuja, jota vastaan asymptoottista käyttäytymistä tutkitaan. Sellaisella väitteellä, jolla ei ole samaa merkitystä, riippuu siitä, seuraaako se "milloin " vai esimerkiksi "(kaikille kiinteille) milloin ".
Luokitus | Sukunimi | Epävirallinen kuvaus | Kun tietystä arvosta ... | Tarkka määritelmä |
---|---|---|---|---|
tai
|
Grand O (Grand Omicron) |
Toiminto | f | rajaa funktio | g | asymptoottisesti, lukuun |
kun k > 0 | |
tai
|
Suuri Omega |
Kaksi määritelmää:
Lukuteorian: |
Lukuusteoriassa: kun k > 0 |
Lukuusteoriassa:
|
Algoritmiteoriassa:
f on aliarvioitu g: llä (tekijään saakka) |
Algoritmiteoriassa:
kun k > 0 |
Algoritmiteoriassa:
|
||
järjestyksessä; Suuri Theta |
f on dominoima ja alistettu g: lle asymptoottisesti |
varten k 1 > 0, ja k 2 > 0 |
|
|
tai
|
Pieni o | f on merkityksetön g : n edessäasymptoottisesti | , mikä tahansa > 0 (kiinteä). | |
Pieni Omega | f hallitsee g asymptoottisesti | kaikille k > 0 | ||
vastaa | f on suunnilleen yhtä suuri kuin g asymptoottisesti | , mikä tahansa > 0 (kiinteä). |
Grand-O: n jälkeen merkintöjä Θ ja Ω käytetään eniten tietojenkäsittelytieteessä; pieni o on yleinen matematiikassa, mutta harvinaisempi tietojenkäsittelytieteessä. Ω on vähän käytetty.
Toinen tietojenkäsittelyssä joskus käytetty merkintätapa on Õ ( pehmeä-O englanniksi), mikä tarkoittaa suurta-o poly-logaritmiseen tekijään asti.
Numeroteoriassa merkinnällä f ( x ) g ( x ) on sama merkitys kuin f ( x ) = Θ ( g ( x )) (jota ei käytetä).
Merkinnät Landau nimetty saksalaisen matemaatikon erikoistunut lukuteoria Edmund Landau joka käytti symboli O , alun perin käyttöön Paul Bachmann , ja innostui keksiä symbolin O . Hän käytti vain merkkiä Ω yhdessä artikkelissa vuonna 1924 merkitsemään ≠ o: ta ; tämän merkinnän olivat ottaneet käyttöön (samalla merkityksellä) vuonna 1914 GH Hardy ja JE Littlewood; Siitä lähtien Ω: ta käytetään yleisesti lukuteoriassa, mutta yksinomaan tässä samassa merkityksessä, eikä koskaan ensimmäisessä merkityksessä, joka on esitetty yllä olevassa taulukossa. Samassa artikkelissa Landau käyttää symboleja Ω R ja Ω L , jotka johtuvat myös Hardystä ja Littlewoodista (ja koska niitä on merkitty Ω + ja Ω - ) vastaavasti . Tietysti se käyttää myös merkintää ∼, mutta ei koskaan ω tai Θ.
Merkinnät Hardy et , käyttöön GH Hardy hänen suolikanavan 1910 Orders of Infinity , on sama rooli kuin Landau Asymptoottisen vertailun toimintoja.
Landau-merkinnöissä voimme määritellä ne seuraavasti:
ja
Hardyn arviot ovat vanhentuneita. Hardy luopui nopeasti omista luokituksistaan; hän käyttää Landaun merkintöjä kaikissa artikkeleissaan (lähes 400!) ja kirjoissaan lukuun ottamatta traktaattiaan vuodelta 1910 ja kolmessa artikkelissa (1910-1913). Voimme huomata, että jos Hardy esitteli vuoden 1910 traktaattiinsa muita symboleja toimintojen asymptoottiseen vertailuun, hän ei koskaan määritellyt tai käyttänyt merkintää (tai ), jotka olemme velkaa Vinogradoville.
Venäläinen numeroteoreetikko Ivan Matvejevich Vinogradov otti 1930-luvulla käyttöön nimensä,
.Vinogradovin ≪-merkintää käytetään yleisesti numeroteoriassa O: n sijasta ; joskus jopa kahta merkintää käytetään keskenään samassa artikkelissa.
Vuonna 1982 Carl Pomerance esitteli uuden merkinnän lyhentämään algoritmien monimutkaisuuden asymptoottisessa tutkimuksessa mukana olevia monimutkaisia toimintoja . Joten esimerkiksi funktio f kuuluu luokkaan, jos meillä on ; eksponentiaalinen "erottaa" toiminnot riittävän niin, että ei ole mahdollista pienentää tätä merkintää esimerkiksi muodostamaan .
Erityisesti Landau-luokitukset johtavat erittäin usein luokituksen väärinkäyttöön, kuten kirjoittamiseen tai huonompaan ; tämä toinen merkintätapa on luettava asetetulla kielellä: kutsumalla merkityksettömien funktioiden joukko kahden funktion suhteen ja erojen joukko , se tarkoittaa sitä . Yleisemmin tämä merkintöjen väärinkäyttö merkitsee sitä, että merkintää (tai jne.) Pidetään funktioluokkana ja merkkinä, joka kuuluu tähän luokkaan.
(en) Big-O-huijaussivu , sivusto, jossa luetellaan algoritmisten monimutkaisuuksien luokittelu toimialueittain.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">