Gfyuki

En matematiko, granda O estas la simbolo O uzata por priskribi asimptotan superan baron por la grandeco de funkcio per la alia, kutime pli simpla, funkcio.

Estas ankaŭ la aliaj simboloj o, Ω, ω, Θ, Õ por diversaj aliaj superaj, subaj kaj striktaj baroj (vidu sube).

Difino |

Estu f(x) kaj g(x) estas du funkcioj sur iu subaro de la reelaj nombroj. Tiam f(x) estas de la ordo de g(x) kiam x proksimiĝas al plus malfinio (kio estas f(x)∈O(g(x)){displaystyle f(x)in {mathcal {O}}(g(x))}) se kaj nur se ekzistas pozitiva reela nombro c kaj reela nombro x₀ tiaj ke |f(x)| < c g(x) por ĉiu x tia ke x>x₀.

Per formuloj ĉi tio estas:

f(x)∈O(g(x)) kun x→+∞{displaystyle f(x)in {mathcal {O}}(g(x)){mbox{ kun }}xto +infty }

se kaj nur se

∃x0,∃c>0 tia ke |f(x)|⩽c|g(x)| por x>x0.{displaystyle exists ;x_{0},exists ;c>0{mbox{ tia ke }}|f(x)|leqslant ;c|g(x)|{mbox{ por }}x>x_{0}.}

La skribmaniero povas ankaŭ esti uzita por priskribi konduton de f(x) proksime al iu reela nombro a:

f(x)∈O(g(x)) kun x→a{displaystyle f(x)in {mathcal {O}}(g(x)){mbox{ kun }}xto a}

se kaj nur se

∃δ>0,∃c>0 tia ke |f(x)|⩽c|g(x)| por |x−a|<δ.{displaystyle exists ;delta >0,exists ;c>0{mbox{ tia ke }}|f(x)|leqslant ;c|g(x)|{mbox{ por }}|x-a|<delta .}

Se g(x) estas ne-nula por valoroj de x sufiĉe proksime al a, ambaŭ ĉi tiuj difinoj povas esti unuece skribitaj per la limigo supera:

f(x))∈O(g(x)) kiam x→a{displaystyle f(x))in {mathcal {O}}(g(x)){mbox{ kiam }}xto a}

se kaj nur se

lim supx→a|f(x)g(x)|<+∞.{displaystyle limsup _{xto a}left|{frac {f(x)}{g(x)}}right|<+infty .}

Uzado |

Granda O skribmaniero estas utila en analizo de rula tempo de algoritmoj.

En matematiko, ambaŭ asimptotaj kondutoj proksime al ∞ kaj proksime al iu a estas uzatadaj. En komputa komplikteorio, nur asimptotoj proksime al ∞ estas uzataj kun nur pozitivaj funkcioj estas konsiderata, tiel la esprimo de absoluta valoro povas esti ellasita el la formuloj de la difino.

Ekzemploj |

Malfinia asimptoto |

Ekzemple, la tempo (aŭ la kvanto de ŝtupoj) bezonata por plenumi problemon de amplekso n estu T(n) = n² - n + 2.

Se n kreskas kaj iĝas grandan, la termo n², estos ĉiam domina, tiel ke ĉiuj alia termoj povas esti neglektitaj. Ekzemple por n=1000, la termo n² estas je 1000 fojoj pli granda ol la termo n. Ignoro de la lasta devas ne havi konsiderindan efikon por plejparto de pritaksoj de rula tempo.

T(n)∈O(n2){displaystyle T(n)in {mathcal {O}}(n^{2})}

Plu, la koeficientoj iĝas negravajn se oni komparas la ordojn. Ekzemple estu termoj n² kaj n³. Eĉ se S(n)=n² kaj U(n)=0,01n³, la lasta estas pli granda ol la unua por n>100. Por plu pli grandaj n, ekzemple n=10⁹, diferenco inter S(n) kaj U(n) estas multe pli granda ol inter U(n) kaj V(n)=n³: S(10⁹)=10¹⁸, U(10⁹)=10²⁵, V(10⁹)=10²⁷.

Tiel la granda O kaptas tion kio restas:

S(n)∈O(n2){displaystyle S(n)in {mathcal {O}}(n^{2})}

U(n)∈O(n3){displaystyle U(n)in {mathcal {O}}(n^{3})}

V(n)∈O(n3){displaystyle V(n)in {mathcal {O}}(n^{3})}

Finia asimptoto |

Granda O povas ankaŭ esti uzata por priskribi la eraran termon en proksimuma kalkulado de funkcio. Ekzemple,

ex=1+x+x22+O(x3)kiam x→0{displaystyle e^{x}=1+x+{frac {x^{2}}{2}}+{mathcal {O}}(x^{3})quad {hbox{kiam}} xto 0}

esprimas la fakton ke la eraro, la diferenco ex−(1+x+x22){displaystyle e^{x}-left(1+x+{frac {x^{2}}{2}}right)}, estas pli malgranda en absoluta valoro ol iu konstanto multiplikita per |x3|{displaystyle left|x^{3}right|} kiam x proksimiĝas al 0.

Problemoj kun la skribmaniero |

O(f(x)) signifas kolekton de funkcioj g(x) de variablo x, tiaj ke ilia kreskado estas limigita per kreskado de f(x) en iu respekto. La tradicia skribmaniero por tio ke g(x) apartenas al ĉi tiu kolekto estas:

g(x) = O(f(x))

Ĉi tiu uzo de la egala signo estas malbona skribmaniero, pro tio ke la pli supra frazo ne estas ekvacio. Estas malvere konkludi de g(x) = O(f(x)) kaj h(x) = O(f(x)) ke g(x)=h(x). Unu el variantoj estas opinii ke ĉi tie "= O" estas unu simbolo. Al eviti la problemon, iuj aŭtoroj preferas skribi anstataŭe kiel:

g(x)∈O(f(x)){displaystyle g(x)in {mathcal {O}}(f(x))}

sen diferenco en signifo. Noto ankaŭ, ke ĉi tie en skribmaniero kun simbolo "=" ne eblas interŝanĝi la flankojn, oni ne skribas kiel

O(f(x)) = g(x)

La komunaj aritmetikaj operacioj estas ofte etenditaj al la klasa koncepto. Ekzemple, h(x) + O(f(x)) signifas kolekton de funkcioj havantaj la kreskadon de h(x) plus parto kies kreskado estas limigita al tiu de f(x). Tial,

g(x)=h(x)+O(f(x)){displaystyle g(x)=h(x)+{mathcal {O}}(f(x))}

estas la samo kiel

g(x)−h(x)∈O(f(x)){displaystyle g(x)-h(x)in {mathcal {O}}(f(x))}

Alia anomalio de la skribmaniero, kvankam malpli escepta, estas ke oni ne eksplicitas kiu variablo estas la funkcia argumento, kaj ĉi tion bezonatas konkludi de la ĉirkaŭteksto se kelkaj variabloj estas koncernataj. En la ekzemplo du dekstraj flankoj kun granda O skribmaniero havas ege malsamajn signifojn:

f(m)=O(mn){displaystyle f(m)={mathcal {O}}(m^{n})}

g(n)=O(mn){displaystyle g(n)={mathcal {O}}(m^{n})}

En la unua okazo f(m) havas polinoman kreskadon, en la dua por m>1, g(n) havas eksponentan kreskadon.

Fina anomalio estas ke la skribmaniero ne montras klare kie la funkcia kreskado estas konsiderata; proksime al iu punkto aŭ al la malfinio. Ĉi tiu estas en kontrasto kun la kutima skribmaniero por limigoj.

En pli kompleksa uzado, O( ) povas aperi en malsamaj lokoj en ekvacio, eĉ kelkfoje en ĉiu flanko. Ekzemple, jeno estas vera por n→∞{displaystyle nto infty }

(n+1)2=n2+O(n){displaystyle (n+1)^{2}=n^{2}+{mathcal {O}}(n)}

(n+O(n1/2))(n+O(logn))2=n3+O(n5/2){displaystyle (n+{mathcal {O}}(n^{1/2}))(n+{mathcal {O}}(log ,n))^{2}=n^{3}+{mathcal {O}}(n^{5/2})}

nO(1)=O(en){displaystyle n^{{mathcal {O}}(1)}={mathcal {O}}(e^{n})}

La signifo de la propozicioj estas: por ĉiuj funkcioj kiu kontentigas ĉiun O( ) maldekstre, estas iuj funkcioj kontentigantaj ĉiun O( ) dekstre, tiaj ke enmeto de ĉi ĉiuj funkcioj en la ekvacion faras la du flankojn egalajn. Ekzemple, la tria ekvacio pli supre signifas ke por ĉiu funkcio f(n)=O(1), estas iu funkcio g(n)=O(eⁿ) tia ke n^f(n)=g(n). En terminoj de la ara skribmaniero kiel pli supre, la signifo estas ke la klaso de funkcioj prezentitaj per la maldekstra flanko estas subaro de la klaso de funkcioj prezentitaj per la dekstra flanko.

Estas ankaŭ problemo ke la simbolo f(x) signifas la valoron de la funkcio f por la argumento x, sed ne la funkcion entute. La simbolo de la funkcio estas f sed ne f(x). Por ĉi tio, iuj aŭtoroj preferas skribi kiel

f∈O(g){displaystyle fin {mathcal {O}}(g)}.

Propraĵoj |

Jen estas listo de klasoj de funkcioj kiuj estas kutime estadas en analizo de algoritmoj. Ĉi tie n pligrandiĝas al malfinio. La pli malrapide kreskantaj funkcioj estas listitigiaj komence. c estas ajna konstanto.

Skribmaniero	Nomo	Ekzemplo de algoritmo kun ĉi tiu tempo
O(1)	Konstanto (konstanta tempo)	Difini ĉu nombro estas para aŭ nepara
O(α(n))	Inverso de akermana funkcio
O(log* n)	Ripetita logaritmo
O(log (log (log n)))
O(log (log n))
O(log n)	Logaritmo	Trovo de ero en ordigita listo per duoniga serĉa algoritmo
O((log n)c) por c>1	Polinomo de logaritmo	Kontrolo ĉu n estas primo per la AKS primeca provo.
O(nc) por 0<c<1	Frakcia potenco
O(n)	Lineara funkcio (lineara tempo)	Adicio de du n-ciferaj nombroj. Trovo de ero en neordigita n-era listo.
O(n log n)		Ordigo de n-era listo per piramida ordigo. Komputo de rapida konverto de Fourier.
O(n2)	Kvadrata funkcio (kvadrata tempo)	Multipliko de du n-ciferaj nombroj (per kutima rekta maniero). Adicio de du n×n matricoj. Ordigo de n-era listo per simpla enenigo aŭ bobelo. Rekta komputo de diskreta konverto de Fourier.
O(n3)	Kuba funkcio (kuba tempo)	Multipliko de du n×n matricoj (per kutima rekta maniero).
O(nc) por c>1 (pli granda ol O(n3) se kaj nur se c>3)	Polinomo (polinoma tempo)	Kontrolo ĉu n-cifera nombro estas primo per la AKS primeca provo. Trovo de la plej mallonga vojo sur pezita orientita grafeo per la algoritmo de Floyd-Warshall
O(cn) por c>1	Eksponenta funkcio, iam nomata kiel geometria (eksponenta tempo)	Trovo de (akurata) solvaĵo por la problemo pri vojaĝa komizo (kun supozo ke P ≠ NP)
O(n!)	Faktorialo, iam nomata kiel kombina funkcio	[1]
O(nn)
O(c1c2n){displaystyle {mathcal {O}}left(c_{1}^{c_{2}^{n}}right)}	Duopa eksponenta funkcio	[2]

Se funkcio f(n) povas esti skribita kiel finia sumo de aliaj funkcioj, tiam la plej rapide kreskanta ero difinas la ordon de f(n). Ekzemple

f(n)=3log⁡n+7(log⁡n)3+4n2+5n3∈O(n3).{displaystyle f(n)=3log n+7(log n)^{3}+4n^{2}+5n^{3}in {mathcal {O}}(n^{3}),!.}

Aparte, se funkcio povas esti barita per polinomo en n, tiam kiel n strebas al malfinio, oni povas malobservi termoj de ne la plej granda ordo de la polinomo.

Por c>1, O(n^c) kaj O(cⁿ) estas tre malsamaj. La lasta kreskas multe, multe pli rapida, sendepende de la konstanto c estas (se ĝi estas pli granda ol unu). Funkcio kiu kreskas pli rapida ol ĉiu potenco de n estas superpolinoma. Funkcio kiu kreskas pli malrapide ol ĉiu eksponenta funkcio de formo cn{displaystyle c^{n}} estas subeksponenta. Funkcio povas esti ambaŭ superpolinoma kaj subeksponenta. Ekzemple ĉi tia estas tempo de ĝenerala nombra kampa kribrilo, la plej rapida sciata algoritmo por entjera faktorigo, kiu por b-bita nombro estas:

O(exp⁡((64b9)13(log⁡b)23)).{displaystyle Oleft(exp left(left({frac {64b}{9}}right)^{1 over 3}(log b)^{2 over 3}right)right).}

O(log(n^c)) estas akurate la samo kiel O(log n). La logaritmoj diferenciĝas nur per konstanta faktoro pro tio ke log(n^c)=c log n kaj tial la granda O ignoras la diferencon. Simile logaritmoj kun malsamaj konstantaj bazoj estas ekvivalentaj. Eksponentoj kun malsamaj bazoj, male, estas ne de la sama ordo. Ekzemple, 2ⁿ kaj 3ⁿ estas ne de la sama ordo.

Por ĉiu k>0 kaj ĉiu c>1, O(n^c log(n^k)) estas subaro de O(log(n^(c+a))) por ĉiu a>0. Tiel ofte estanta kresko O(n^c log(n^k)) povas esti konsiderata kiel polinoma kun malmulte pli granda potenco.

Multipliko de la variablo per konstanto povas afekti aŭ ne afekti la ordon de la kresko. Ekzemple, se la ordo estas n², anstataŭigo de n per cn signifas ordon de c²n², kaj la granda O ignoras la konstanton c². Ĉi tio povas esti skribita kiel c2n2∈O(n2){displaystyle c^{2}n^{2}in {mathcal {O}}(n^{2})}. Tamen se la ordo estas 2ⁿ, anstataŭigo de n per cn donas ordon 2cn=(2c)n{displaystyle 2^{cn}=(2^{c})^{n}}, kiu ne estas ekvivalento al 2ⁿ (se c≠1).

Ŝanĝo de la variablo povas ŝanĝi la formulon por ordo de kresko, ne ŝanĝante la realan tempon de ruligo. Ekzemple por AKS primeca provo, la tempo estas O((log n)^c) se n estas la kontrolata nombro kaj O(n^c) se n estas kvanto de ciferoj en la nombro.

Eblas pli granda kreskado ol komune estantaj, ekzemple la solo-valora versio de la akermana funkcio, A(n,n). Male, estadas ege malrapide kreskantaj funkcioj, ekzemple la inverso de ĉi tiu funkcio A(n,n), ofte skribata kiel α(n). Kvankam α(n) estas nebarita (proksimiĝas al malfinio kiam n proksimiĝas al malfinio), ĉi tiaj funkcioj estas ofte proksimumataj kiel konstantaj faktoroj por ĉiuj praktikaj celoj.

Produto |

f1∈O(g1) ∧ f2∈O(g2)⟹f1f2∈O(g1g2){displaystyle f_{1}in {mathcal {O}}(g_{1}) wedge f_{2}in {mathcal {O}}(g_{2}),implies f_{1}f_{2}in {mathcal {O}}(g_{1}g_{2}),}

f⋅O(g)∈O(fg){displaystyle fcdot {mathcal {O}}(g)in {mathcal {O}}(fg)}

Sumo |

f1∈O(g1) ∧ f2∈O(g2)⟹f1+f2∈O(g1+g2){displaystyle f_{1}in {mathcal {O}}(g_{1}) wedge f_{2}in {mathcal {O}}(g_{2}),implies f_{1}+f_{2}in {mathcal {O}}(g_{1}+g_{2}),}

Ĉi tiu implicas f1∈O(g)∧f2∈O(g)⟹f1+f2∈O(g){displaystyle f_{1}in {mathcal {O}}(g)land f_{2}in {mathcal {O}}(g)implies f_{1}+f_{2}in {mathcal {O}}(g)}, kio signifas ke O(g){displaystyle O(g)} estas konveksa konuso.

f+O(g)∈O(f+g){displaystyle f+{mathcal {O}}(g)in {mathcal {O}}(f+g)}

Multipliko per konstanto |

Por k∈R>0{displaystyle kin mathbb {R} _{>0}}.

O(k⋅g)=O(g){displaystyle {mathcal {O}}(kcdot g)={mathcal {O}}(g)}

f∈O(g)⇒k⋅f∈O(g){displaystyle fin {mathcal {O}}(g)Rightarrow kcdot fin {mathcal {O}}(g)}

Rilatantaj asimptotaj rilatoj |

Malgranda o |

La rilato f(x)∈o(g(x)){displaystyle f(x)in o(g(x))} signifas ke f(x) kreskas multe pli malrapide ol g(x), do la limigo de f(x)/g(x) estas nulo, kiam x proksimiĝas malfinio aŭ al certa valoro.

Ekzemple por x→∞{displaystyle xto infty }:

• 2x∈o(x2){displaystyle 2xin o(x^{2}),!}


• 2x2∉o(x2){displaystyle 2x^{2}not in o(x^{2})}


• 1/x∈o(1){displaystyle 1/xin o(1)}

Jenaj propraĵoj ekzistas:

• o(f)+o(f)⊆o(f){displaystyle o(f)+o(f)subseteq o(f)}


• o(f)o(g)⊆o(fg){displaystyle o(f)o(g)subseteq o(fg)}


• o(o(f))⊆o(f){displaystyle o(o(f))subseteq o(f)}


• 
  o(f)⊂O(f){displaystyle o(f)subset O(f)} kaj tial la propraĵoj de O aplikas kun kombinaĵoj de o kaj O.

Simile al granda O, la frazo "f(x) estas o(g(x))" estas kutime skribata kiel f(x) = o(g(x)), kio estas malbona skribmaniero.

Aliaj |

Skribmaniero	Priskribo	Difino
f(n)∈O(g(n)){displaystyle f(n)in {mathcal {O}}(g(n))}	f estas asimptote desupre barita per g kun ignoro de konstanta faktoro	∃(C>0),n0:∀(n>n0)|f(n)|≤|Cg(n)|{displaystyle exists (C>0),n_{0}:forall (n>n_{0});|f(n)|leq |Cg(n)|}
f(n)∈Ω(g(n)){displaystyle f(n)in Omega (g(n))}	f estas asimptote desube barita per g kun ignoro de konstanta faktoro	∃(C>0),n0:∀(n>n0)|Cg(n)|≤|f(n)|{displaystyle exists (C>0),n_{0}:forall (n>n_{0});|Cg(n)|leq |f(n)|}
f(n)∈Θ(g(n)){displaystyle f(n)in Theta (g(n))}	f estas barita strikte (desube kaj desupre) per g asimptote	∃(C,D>0),n0:∀(n>n0)|Cg(n)|<|f(n)|<|Dg(n)|{displaystyle exists (C,D>0),n_{0}:forall (n>n_{0});|Cg(n)|<|f(n)|<|Dg(n)|}
f(n)∈o(g(n)){displaystyle f(n)in o(g(n))}	f estas dominita per g asimptote	∀(C>0),∃n0:∀(n>n0)|f(n)|<|Cg(n)|{displaystyle forall (C>0),exists n_{0}:forall (n>n_{0});|f(n)|<|Cg(n)|}
f(n)∈ω(g(n)){displaystyle f(n)in omega (g(n))}	f dominas na g asimptote	∀(C>0),∃n0:∀(n>n0)|Cg(n)|<|f(n)|{displaystyle forall (C>0),exists n_{0}:forall (n>n_{0});|Cg(n)|<|f(n)|}
f(n)∼g(n){displaystyle f(n)sim g(n)}	f kaj g asimptote egalas	limn→∞f(n)g(n)=1{displaystyle lim _{nto infty }{frac {f(n)}{g(n)}}=1}
f(n)=O~(g(n)){displaystyle f(n)={tilde {O}}(g(n))} (Õ estas la mola-O)	Same kiel granda O, sed ignoranta logaritmajn faktorojn.	f(n)=O(g(n)logk⁡g(n)){displaystyle f(n)=O(g(n)log ^{k}g(n))} por iu k.

logk⁡n{displaystyle log ^{k}n} estas ĉiam o(na){displaystyle o(n^{a})} por ĉiu konstanto k kaj ĉiu konstanto a>0.

La L-skribmaniero, difinita kiel

Ln[α,c]=O(e((c+o(1))(ln⁡n)α(ln⁡ln⁡n)1−α)){displaystyle L_{n}[alpha ,c]=Oleft(e^{((c+o(1))(ln n)^{alpha }(ln ln n)^{1-alpha })}right)},

estas oportuna por funkcioj kiuj estas inter polinomo kaj eksponenta funkcio.

Multaj variabloj |

Granda O kaj malgranda o, kaj la aliaj povas ankaŭ esti uzataj kun multaj variabloj. Ekzemple, la frazo

f(n,m)=n2+m3+O(n+m) kun n,m→∞{displaystyle f(n,m)=n^{2}+m^{3}+{hbox{O}}(n+m){mbox{ kun }}n,mto infty }

asertas ke ekzistas konstantoj C kaj N tiaj ke

∀n,m>N:|f(n,m)−(n2+m3)|≤C(n+m).{displaystyle forall n,m>N:|f(n,m)-(n^{2}+m^{3})|leq C(n+m).}

Por konkreteco la ŝanĝanta variablo devus ĉiam esti precizigita: la frazo

f(n,m)=O(nm) kun n,m→∞{displaystyle f(n,m)={hbox{O}}(n^{m}){mbox{ kun }}n,mto infty }

estas sufiĉe malsama de

∀m:f(n,m)=O(nm) kun n→∞.{displaystyle forall m:f(n,m)={hbox{O}}(n^{m}){mbox{ kun }}nto infty .}

Vidu ankaŭ |

• Rapida ordigo

Referencoj |

1. 
   ↑ [1]
   


2. 
   ↑ Komplikeco de duopa eksponenta funkcio en komputado
   

Eksteraj ligiloj |

• Enkonduko al asimptotaj skribmanieroj


• 
  Vikilibroj pri granda O
  


• 
  Donald Knuth. Granda Omicron kaj granda Omego kaj granda Θ, ACM SIGACT Novaĵoj, Volumeno 8, Eldono 2, 1976.


• Formaligo de O skribmaniero


• Granda O skribmaniero


• Malgranda o skribmaniero


• "Ω"


• "ω"


• "Θ"