Asymptotické srovnání

Nechť f a g jsou dvě funkce reálné proměnné x . Říkáme, že f dominuje g v + ∞ , nebo že g dominuje f v + ∞ , a označujeme (Bachmann, 1894, nebo Landau, 1909 notace)

F(X)=Ó(G(X)) (X→∞),{\ displaystyle f (x) = O (g (x)) \ (x \ rightarrow \ infty),}

nebo (Hardyho notace, 1910, zastaralé)

 F≼G,{\ displaystyle \ f \ preccurlyeq g,}

nebo znovu (Vinogradovova notace, 30. léta)

F(X)≪G(X) (X→∞),{\ Displaystyle f (x) \ ll g (x) \ (x \ rightarrow \ infty),}

když existují konstanty N a C takové, že

∀X>NE|F(X)|≤VS|G(X)|.{\ displaystyle \ forall x> N \ qquad \ left | f (x) \ right | \ leq C \ left | g (x) \ right |.}

Intuitivně to znamená, že f neroste rychleji než g .

Stejně tak, pokud a je reálné číslo, píšeme

F(X)=ÓX→na(G(X)){\ displaystyle f (x) = {\ podmnožina {x \ to a} {O}} (g (x))}

pokud existují konstanty d > 0 a C takové, že

∀X|X-na|<d⇒|F(X)|≤VS|G(X)|.{\ displaystyle \ forall x \ qquad \ left | xa \ right | <d \ Rightarrow \ left | f (x) \ right | \ leq C \ left | g (x) \ right |.}

• 4X3+10 000X2=ÓX→∞(X3).{\ displaystyle 4x ^ {3} + 10 000x ^ {2} = {\ podmnožina {x \ to \ infty} {O}} (x ^ {3}).}
• X3=ÓX→∞(4X3+10 000X2).{\ displaystyle x ^ {3} = {\ podmnožina {x \ to \ infty} {O}} (4x ^ {3} + 10 000x ^ {2}).}
• V bodě a , je-li f zanedbatelné před g nebo ekvivalentní g , pak mu dominuje g .
• Funkce f je ohraničená na okolí tehdy a jen tehdy, jestliže .F(X)=ÓX→na(1){\ displaystyle f (x) = {\ podmnožina {x \ to a} {O}} (1)}

Absence převahy a oscilací

Hardyho a Littlewoodova Ω notace (teorie čísel)

V roce 1914 představili Hardy a Littlewood nový symbol Ω definovaný takto:

F(X)=Ω(G(X)) (X→∞)⇔lim supX→∞|F(X)G(X)|>0{\ Displaystyle f (x) = \ Omega (g (x)) \ (x \ rightarrow \ infty) \; \ Leftrightarrow \; \ limsup _ {x \ to \ infty} \ left | {\ frac {f (x )} {g (x)}} \ vpravo |> 0}

Funkce f a g jsou považovány za definované a g pozitivní v sousedství nekonečna. Taková je i negace . F(X)=Ω(G(X)){\ displaystyle f (x) = \ Omega (g (x))}F(X)=Ó(G(X)){\ displaystyle f (x) = o (g (x))}

V roce 1916 představili stejní autoři dva nové symboly Ω R a Ω L , definované takto:

F(X)=ΩR(G(X)) (X→∞)⇔lim supX→∞F(X)G(X)>0{\ displaystyle f (x) = \ Omega _ {R} (g (x)) \ (x \ rightarrow \ infty) \; \ Leftrightarrow \; \ limsup _ {x \ to \ infty} {\ frac {f ( x)} {g (x)}}> 0}

F(X)=ΩL(G(X)) (X→∞)⇔lim infX→∞F(X)G(X)<0{\ displaystyle f (x) = \ Omega _ {L} (g (x)) \ (x \ rightarrow \ infty) \; \ Leftrightarrow \; \ liminf _ {x \ to \ infty} {\ frac {f ( x)} {g (x)}} <0}

Stejně jako dříve se předpokládá, že funkce f a g jsou definovány a g pozitivní v sousedství nekonečna. Takže je negace a negace . F(X)=ΩR(G(X)){\ displaystyle f (x) = \ Omega _ {R} (g (x))}F(X)<Ó(G(X)){\ displaystyle f (x) <o (g (x))}F(X)=ΩL(G(X)){\ displaystyle f (x) = \ Omega _ {L} (g (x))}F(X)>Ó(G(X)){\ displaystyle f (x)> o (g (x))}

Na rozdíl od toho, co později tvrdil DE Knuth , použil Edmund Landau v roce 1924 také tyto tři symboly.

Tyto Hardyho a Littlewoodovy notace jsou prototypy, které se po Landauovi zdají být nikdy použity jako takové: Ω R se stalo Ω + a Ω L se stalo Ω - .

Tyto tři symboly jsou nyní běžně používají v analytické teorie čísel , stejně jako znamenat, že podmínky a jsou oba spokojeni. F(X)=Ω±(G(X)){\ displaystyle f (x) = \ Omega _ {\ pm} (g (x))}F(X)=Ω+(G(X)){\ displaystyle f (x) = \ Omega _ {+} (g (x))}F(X)=Ω-(G(X)){\ displaystyle f (x) = \ Omega _ {-} (g (x))}

Je zřejmé, že v každém z těchto definic, můžeme nahradit ∞ od -∞ nebo reálné číslo.

Jednoduché příklady

My máme

hřích⁡X=Ω(1) (X→∞){\ displaystyle \ sin x = \ Omega (1) \ (x \ rightarrow \ infty)}

a přesněji

hřích⁡X=Ω±(1) (X→∞).{\ displaystyle \ sin x = \ Omega _ {\ pm} (1) \ (x \ rightarrow \ infty).}

My máme

hřích⁡X+1=Ω(1) (X→∞){\ Displaystyle \ sin x + 1 = \ Omega (1) \ (x \ rightarrow \ infty)}

a přesněji

hřích⁡X+1=Ω+(1) (X→∞) ;{\ displaystyle \ sin x + 1 = \ Omega _ {+} (1) \ (x \ rightarrow \ infty) ~;}

nicméně,

hřích⁡X+1≠Ω-(1) (X→∞).{\ displaystyle \ sin x + 1 \ not = \ Omega _ {-} (1) \ (x \ rightarrow \ infty).}

Dvě nekompatibilní definice

Je důležité zdůraznit skutečnost, že psaní

F(X)=Ω(G(X)) (X→∞){\ Displaystyle f (x) = \ Omega (g (x)) \ (x \ rightarrow \ infty)}

má dvě nekompatibilní definice v matematice, obě velmi rozšířené, jednu v teorii analytických čísel , kterou jsme právě představili, druhou v teorii složitosti algoritmů . Když se tyto dvě disciplíny setkají, je pravděpodobné, že tato situace způsobí velký zmatek.

Knuthova definice

V roce 1976 publikoval Knuth článek, jehož hlavním účelem bylo ospravedlnit jeho použití stejného symbolu Ω k popisu jiné vlastnosti, než kterou popsali Hardy a Littlewood. Snaží se přesvědčit čtenáře, že definice Hardyho a Littlewooda se téměř nepoužívá (což se i v roce 1976 stejně mýlí už 25 let). Jde tak daleko, že tvrdí, že Landau to nikdy nepoužil (což je také nepravdivé). Naléhavě cítí potřebu jiného pojmu ( „  Pro všechny aplikace, které jsem dosud viděl v informatice, je mnohem vhodnější silnější požadavek […]  “ ) a rozhodl se, že k popisu musí být vyhrazeno použití symbolu Ω to. Je silně rozrušený starou definicí ( „  Bohužel Hardy a Littlewood nedefinovali Ω ( f ( n )), jak jsem chtěl  “ ).

Riskuje tedy riziko vzniku zmatku a definuje

F(X)=Ω(G(X))⇔G(X)=Ó(F(X)){\ displaystyle f (x) = \ Omega (g (x)) \ levá šipka g (x) = O (f (x))}

Pomocí srovnání

Omezený vývoj

V matematice je často důležité sledovat chybný termín aproximace. Tato notace se používá zejména při řešení omezeného vývoje a výpočtech ekvivalentů. Například expanzi exponenciální funkce do řádu 2 lze také zapsat:

EX=1+X+12X2+Ó(X2) qunaned X→0{\ displaystyle e ^ {x} = 1 + x + {\ frac {1} {2}} x ^ {2} + o (x ^ {2}) \ {\ rm {když}} \ x \ rightarrow 0 }

vyjádřit skutečnost, že chyba, rozdíl , je zanedbatelná dříve, když má tendenci k 0. EX-(1+X+X22){\ displaystyle e ^ {x} - \ vlevo (1 + x + {\ frac {x ^ {2}} {2}} \ vpravo)}X2{\ displaystyle x ^ {2}}X{\ displaystyle x}

Je třeba poznamenat, že počet operandů v tomto typu zápisu musí být omezen konstantou, která nezávisí na proměnné: například tvrzení je zjevně nepravdivé, pokud elipsa skrývá řadu výrazů, které tomu tak není, není omezena, když x se liší. Ó(X)+Ó(X)+⋯+Ó(X)=Ó(X){\ displaystyle o (x) + o (x) + \ tečky + o (x) = o (x)}

Srovnávací stupnice

Zde je seznam kategorií funkcí běžně používaných při analýze. Proměnná (zde uvedená n ) má sklon k + ∞ a c je libovolná reálná konstanta. Když je c konstanta větší než 1, objeví se funkce v tomto seznamu ve vzestupném pořadí.

O ( n c ) a O ( c n ) se velmi liší. Ten umožňuje mnohem rychlejší růst, a to pro každou konstantu c > 1. Funkce, která roste rychleji než jakýkoli polynom, se říká superpolynomiální . Funkce, která roste pomaleji než jakákoli exponenciální, je považována za subexponenciální . Existují jak superpolynomiální, tak subexponenciální funkce, jako je například funkce n log ( n ) .

Všimněte si také, že O (log n ) je přesně stejné jako O (log ( n c )), protože tyto dva logaritmy jsou navzájem násobné konstantním faktorem a že notace s velkým O „ignoruje“ multiplikativní konstanty . Podobně logaritmy v různých konstantních základnách jsou ekvivalentní.

Předchozí seznam je užitečný z důvodu následující vlastnosti: je-li funkce f součet funkcí a pokud jedna z funkcí součtu roste rychleji než ostatní, určuje pořadí růstu f ( n ).

Příklad:

Funkce více proměnných

Tuto notaci lze také použít s funkcemi několika proměnných:

Psaní:	F(ne,m)=ne2+m3+Ó(ne+m){\ displaystyle f (n, m) = n ^ {2} + m ^ {3} + O (n + m) \;} když m,ne→+∞{\ displaystyle m, n \ až + \ infty}
odpovídá tvrzení:	∃VS∃NE∀ne,m>NE|F(ne,m)-ne2-m3|≤VS(ne+m){\ displaystyle \ existuje C \ quad \ existuje N \ quad \ forall n, m> N \ qquad | f (n, m) -n ^ {2} -m ^ {3} | \ leq C (n + m) }

Pro některé tato notace zneužívá symbol rovnosti, protože se zdá, že porušuje axiom rovnosti  : „věci stejné se rovnají sobě navzájem“ (jinými slovy, s touto notací je rovnost n 'spíše rovnocenností. vztah ). Můžeme to však vzít v úvahu i písemně

F(ne,m)-ne2-m3=Ó(ne+m),{\ displaystyle f (n, m) -n ^ {2} -m ^ {3} = O (n + m),}

notace "= O" označuje jediný operátor, při jehož psaní znak "=" nemá svou vlastní nezávislou existenci (a zejména neoznačuje vztah ekvivalence). V tomto případě již nedochází ke zneužití hodnocení, ale zjevně stále existuje riziko záměny. Je také možné definovat O ( g ( x )) jako sadu funkcí, jejichž prvky jsou všechny funkce, které nerostou rychleji než g , a použít množinové notace k označení, zda je daná funkce prvkem množiny, tedy definované. Například :

F(ne,m)-ne2-m3∈Ó(ne+m),{\ displaystyle f (n, m) -n ^ {2} -m ^ {3} \ v O (n + m),}

Obě smlouvy jsou běžně používané, ale první (a nejstarší) je až do začátku XXI th  nejčastěji vyskytují století. Abychom se tomuto problému vyhnuli, používáme (stejně běžně) vinogradovskou notaci (viz níže).

F(ne,m)-ne2-m3≪ne+m,{\ displaystyle f (n, m) -n ^ {2} -m ^ {3} \ ll n + m,}

Dalším problémem je, že je nutné jasně označit proměnnou, proti které se zkoumá asymptotické chování. Tvrzení, jako například, nemá stejný význam v závislosti na tom, zda za ním následuje „kdy  “ nebo například „(pro jakékoli pevné) kdy  “. F(ne,m)=Ó(mne){\ displaystyle f (n, m) = O (m ^ {n}) \;}m,ne→+∞{\ displaystyle m, n \ až + \ infty}m{\ displaystyle m}ne→+∞{\ displaystyle n \ až + \ infty}

Landauova rodina zápisů O , o , Ω, ω, Θ, ~

Hodnocení	Příjmení	Neformální popis	Když z určité pozice ... ne→∞{\ displaystyle n \ až \ infty}	Přísná definice
F(ne)=Ó(G(ne)){\ displaystyle f (n) = O (g (n))} nebo F(ne)∈Ó(G(ne)){\ displaystyle f (n) \ v O (g (n))}	Grand O (Grand Omicron)	Funkce | f | je ohraničen funkcí | g | asymptoticky, až na jeden faktor	|F(ne)|≤|G(ne)|⋅k{\ displaystyle | f (n) | \ leq | g (n) | \ cdot k}pro k > 0	∃k>0,∃ne0∀ne>ne0|F(ne)|≤|G(ne)|⋅k{\ displaystyle \ existuje k> 0, \ existuje n_ {0} \; \ forall n> n_ {0} \; | f (n) | \ leq | g (n) | \ cdot k}
F(ne)=Ω(G(ne)){\ Displaystyle f (n) = \ Omega (g (n))} nebo F(ne)∈Ω(G(ne)){\ Displaystyle f (n) \ v \ Omega (g (n))}	Velká Omega	Dvě definice: V teorii čísel: f není zanedbatelné ve srovnání s g	V teorii čísel: |F(nei)|≥|G(nei)|⋅k{\ displaystyle | f (n_ {i}) | \ geq | g (n_ {i}) | \ cdot k}pro k > 0 a pro posloupnost číselnei→∞{\ displaystyle n_ {i} \ rightarrow \ infty}	V teorii čísel: ∃k>0,∀ne0∃ne>ne0|G(ne)|⋅k≤|F(ne)|{\ displaystyle \ existuje k> 0, \ forall n_ {0} \; \ existuje n> n_ {0} \; | g (n) | \ cdot k \ leq | f (n) |}
		V teorii algoritmů: f je podhodnoceno g (až na faktor) (kde f dominuje g )	V teorii algoritmů: |F(ne)|≥|G(ne)|⋅k{\ displaystyle | f (n) | \ geq | g (n) | \ cdot k}pro k > 0	V teorii algoritmů: ∃k>0,∃ne0∀ne>ne0|G(ne)|⋅k≤|F(ne)|{\ displaystyle \ existuje k> 0, \ existuje n_ {0} \; \ pro všechny n> n_ {0} \; | g (n) | \ cdot k \ leq | f (n) |}
F(ne)∈Θ(G(ne)){\ displaystyle f (n) \ in \ théta (g (n))}	řádu; Skvělá théta	f dominuje a jeasymptoticky vystaven g	|G(ne)|⋅k1≤|F(ne)|≤|G(ne)|⋅k2{\ displaystyle | g (n) | \ cdot k_ {1} \ leq | f (n) | \ leq | g (n) | \ cdot k_ {2}} pro k 1 > 0 a k 2 > 0	∃k1,k2>0,∃ne0∀ne>ne0{\ displaystyle \ existuje k_ {1}, k_ {2}> 0, \ existuje n_ {0} \; \ pro všechny n> n_ {0}} |G(ne)|⋅k1<|F(ne)|<|G(ne)|⋅k2{\ displaystyle | g (n) | \ cdot k_ {1} <| f (n) | <| g (n) | \ cdot k_ {2}}
F(ne)=Ó(G(ne)){\ displaystyle f (n) = o (g (n))} nebo F(ne)∈Ó(G(ne)){\ Displaystyle f (n) \ in o (g (n))}	Malé o	f je před g asymptoticky zanedbatelné	|F(ne)|≤|G(ne)|⋅ε{\ displaystyle | f (n) | \ leq | g (n) | \ cdot \ varepsilon}, cokoli > 0 (pevné). ε{\ displaystyle \ varepsilon}	∀ε>0∃ne0∀ne>ne0|F(ne)|≤|G(ne)|⋅ε{\ displaystyle \ forall \ varepsilon> 0 \; \ existuje n_ {0} \; \ forall n> n_ {0} \; | f (n) | \ leq | g (n) | \ cdot \ varepsilon}
F(ne)∈ω(G(ne)){\ Displaystyle f (n) \ in \ omega (g (n))}	Malá Omega	f dominuje g asymptoticky	|F(ne)|≥|G(ne)|⋅k{\ displaystyle | f (n) | \ geq | g (n) | \ cdot k}pro všechna k > 0	∀k>0∃ne0∀ne>ne0|G(ne)|⋅k≤|F(ne)|{\ displaystyle \ forall k> 0 \; \ existuje n_ {0} \; \ forall n> n_ {0} \; | g (n) | \ cdot k \ leq | f (n) |}
F(ne)∼G(ne){\ Displaystyle f (n) \ sim g (n) \!}	ekvivalentní	f je přibližně rovno g asymptoticky	|F(ne)-G(ne)|<ε|G(ne)|{\ displaystyle | f (n) -g (n) | <\ varepsilon | g (n) |}, cokoli > 0 (pevné). ε{\ displaystyle \ varepsilon}	∀ε>0∃ne0∀ne>ne0|F(ne)-G(ne)|<ε|G(ne)|{\ displaystyle \ forall \ varepsilon> 0 \; \ existuje n_ {0} \; \ forall n> n_ {0} \; | f (n) -g (n) | <\ varepsilon | g (n) |}

Po grand-O jsou notace Θ a Ω nejpoužívanější v počítačové vědě; malé-o je běžné v matematice, ale vzácnější v počítačové vědě. Ω je málo používaný.

Další notace, která se někdy používá v informatice, je Õ ( soft-O v angličtině), což znamená velký-o až po polylogaritmický faktor.

V teorii čísel má zápis f ( x ) g ( x ) stejný význam jako f ( x ) = Θ ( g ( x )) (který se nepoužívá). ≍{\ displaystyle \ asymp}

Systémy hodnocení

Landauovy notace

Tyto zápisy Landau pojmenované po německém matematikovi specializující se teorie čísel Edmund Landau , který používal symbol O , původně zavedený Paul Bachmann , a byl inspirován vynalézt symbol O . Symbol Ω použil pouze v jednom článku v roce 1924, aby označil ≠ o ; tato notace byla zavedena (se stejným významem) v roce 1914 GH Hardy a JE Littlewood; Od té doby se Ω běžně používá v teorii čísel, ale výhradně ve stejném smyslu a nikdy v prvním smyslu uvedeném v tabulce výše. Ve stejném článku Landau používá symboly Ω R a Ω L , a to i vzhledem k Hardy a Littlewood, (a od označené W + a W - ) k označení , v tomto pořadí . Samozřejmě také používá notaci ∼, ale nikdy ω nebo Θ. ≮Ó{\ displaystyle \ ne <o}≯Ó{\ displaystyle \ not> o}

Hardyho notace

Tyto zápisy Hardy et zavedená GH Hardy v jeho traktu 1910 objednávek nekonečna hrát stejnou roli jako ti Landau pro asymptoticky srovnání funkcí. ≼{\ displaystyle \ preccurlyeq}≺{\ displaystyle \ prec}

V Landauově notaci je můžeme definovat takto:

F≼G⟺F=Ó(G){\ Displaystyle f \ preccurlyeq g \ iff f = O (g)}

a

F≺G⟺F=Ó(G).{\ Displaystyle f \ prec g \ iff f = o (g).}

Hodnocení Hardyho jsou zastaralá. Hardy rychle opustil své vlastní hodnocení; používá Landauovy notace ve všech svých článcích (téměř 400!) a ve svých knihách s výjimkou traktátu z roku 1910 a ve 3 článcích (1910-1913). Můžeme si povšimnout, že pokud Hardy představil ve svém úryvku z roku 1910 některé další symboly pro asymptotické srovnání funkcí, nikdy nedefinoval ani nepoužíval notaci (nebo ), které dlužíme Vinogradovovi. ≪{\ displaystyle \ ll}≺≺{\ displaystyle \ prec \! \! \ prec}

Vinogradovova notace

Ruský teoretik čísel Ivan Matveyevich Vinogradov představil ve 30. letech notaci, která nese jeho jméno,

F≪G⟺F=Ó(G){\ Displaystyle f \ ll g \ iff f = O (g)}

Vinogradovova notace se běžně používá v teorii čísel namísto O ; někdy dokonce dva zápisy jsou zaměnitelně použity ve stejném článku.

L notace

V roce 1982 zavedl Carl Pomerance nový zápis, který má zkrátit komplexní funkce spojené s asymptotickým studiem složitosti algoritmů . Například funkce f patří do třídy, pokud máme  ; exponenciální „odděluje“ funkce dostatečně, takže není možné tento zápis například zredukovat na formu . Lne[α,vs.]{\ displaystyle L_ {n} [\ alfa, c]}F=exp⁡((vs.+Ó(1))log⁡(ne)α(log⁡log⁡ne)1-α){\ Displaystyle f = \ exp \ left ((c + o (1)) \ log (n) ^ {\ alpha} (\ log \ log n) ^ {1- \ alpha} \ right)}F=Ó(G){\ displaystyle f = O (g)}

Zneužití hodnocení

Hodnocení Landau zejména vede k velmi častému zneužívání hodnocení, jako je psaní nebo horší  ; Tento druhý zápis je třeba číst za použití nastaveného jazyka: voláním sadu funkcí zanedbatelné vzhledem k a sady rozdílů dvou funkcí , to znamená, že . Obecněji se toto zneužití notace považuje za považování notace (nebo atd.) Za představující třídu funkcí a za význam, který do této třídy patří. F=Ó(G)⇒2F=Ó(G){\ displaystyle f = o (g) \ Rightarrow 2f = o (g)}Ó(G)-Ó(G)=Ó(G){\ displaystyle o (g) -o (g) = o (g)}NA{\ displaystyle A}G{\ displaystyle g}B=NA-NA{\ displaystyle B = AA}NA{\ displaystyle A}B⊂NA{\ displaystyle B \ podmnožina A}Ó(G){\ displaystyle o (g)}Ó(G){\ displaystyle O (g)}F=Ó(G){\ displaystyle f = O (g)}F{\ displaystyle f}

Poznámky a odkazy

1. (en) GH Hardy, „Infinitärcalcül“ Paula du Bois-Reymonda,  „Cambridge Tracts in Mathematics, 12, 1910, druhé vydání 1924. Číst online [PDF] .
2. (de) Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen , Berlín 1909, str. 883.
3. (en) GH Hardy a EM Wright , Úvod do teorie čísel ( 1 st  ed. 1938) [ Maloobchodní Edition ], 4 th ed., P.  7 .
4. Ačkoli ještě uvedeno v 4 th  vydání Hardy a Wright, s. 7, protože se občas používá, ve skutečnosti se ve zbytku práce nikdy nepoužívá, kde se autoři systematicky uchylují k ekvivalentní notaci o . Sám Hardy tuto notaci nikdy nepoužíval ve svých pracích publikovaných po roce 1913.
5. Abychom se této podmínce vyhnuli, můžeme nahradit následující definici slovy „Říkáme, že pokud existuje funkce taková a “; toto rozšíření definice je však málo praktické.F(X)=ÓX→na(G(X)){\ displaystyle f (x) = {\ underset {\ overset {x \ rightarrow a} {}} {o}} (g (x))}ϵ(X){\ displaystyle \ epsilon (x)}F(X)=ϵ(X)G(X){\ displaystyle f (x) = \ epsilon (x) g (x)}limX→naϵ(X)=0{\ displaystyle \ lim _ {x \ až a} \ epsilon (x) = 0}
6. E. Ramis, C. Deschamp a J. Odoux, kurz speciální matematiky , svazek 3, s. 148
7. Viz odstavec # Zneužití notace níže
8. (en) Donald Knuth, „  Velký Omicron a velká Omega a velká Theta  “, SIGACT News , duben-červen 1976, s. 18–24 [ číst online ] [PDF] .
9. (en) GH Hardy a JE Littlewood, „Některé problémy diofantické aproximace“, Acta Mathematica , sv. 37, 1914, str. 225
10. (en) GH Hardy a JE Littlewood, „Příspěvek k teorii Riemannovy zeta-funkce a teorii distribuce prvočísel“, Acta Mathematica , sv. 41, 1916.
11. (de) E. Landau, „Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV “, Nachr. Gesell. Wiss. Gött. Matematika Kl. , 1924, s. 137-150
12. (in) EC Titchmarsh, Theory of the Riemann Zeta-Function , Oxford, Clarendon Press, 1951
13. Ospravedlnil se tím, že napsal: „  Ačkoli jsem změnil Hardyho a Littlewoodovu definici Ω, cítím se oprávněný, protože to není v žádném případě široce používáno, a protože existují i ​​jiné způsoby, jak říci, co chtějí říci v poměrně vzácné případy, kdy platí jejich definice.  "
14. Zahlentheorie , svazek 2, 1894, s. 402.
15. Viz například (v) GH Hardy a EM Wright , Úvod do teorie čísel ( 1 st  ed. 1938) [ Maloobchodní Edition ].
16. Viz například „Nový odhad pro G ( n ) ve Waringově problému“ (v ruštině), Doklady Akademii Nauk SSSR , sv. 5, č. 5-6, 1934, s. 249-253. Překlad do angličtiny v: Vybraná díla / Ivan Matveevič Vinogradov; připravil Steklovův matematický ústav Akademie věd SSSR u příležitosti jeho 90. narozenin , Springer-Verlag, 1985.

Podívejte se také

Související články

• Asymptotický vývoj
• Asymptotická funkce
• Rychlost konvergence sad
• Srovnávací stupnice
• Analytická kombinatorika

Externí odkaz

(en) Big-O Cheat Sheet , web obsahující klasifikaci algoritmických složitostí podle domény.