Granda O: Malsamoj inter versioj
| [nekontrolita versio] | [nekontrolita versio] |
Enhavo forigita Enhavo aldonita
KuBOT (diskuto | kontribuoj) e Anstataŭigo de ne plu uzota Ŝablono:EL; vidu VP:DT en Marto 2017 |
e Kelkaj rudimentaj lingvaj korektoj |
||
Linio 19:
:<math>\exists \;x_0,\exists \;c>0\mbox{ tia ke } |f(x)| \leqslant \; c |g(x)|\mbox{ por }x>x_0.</math>
:<math>f(x) \in \mathcal{O}(g(x))\mbox{ kun }x\to a</math>
Linio 37:
== Uzado ==
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.
Linio 67:
esprimas la fakton ke la eraro, la diferenco <math>e^x - \left(1 + x +\frac{x^2}{2}\right)</math>, estas pli malgranda en [[absoluta valoro]] ol iu konstanto multiplikita per <math>\left|x^3\right|</math> kiam ''x'' proksimiĝas al 0.
== Problemoj
''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
: ''g(x) = O(f(x))''
Ĉi tiu uzo de la [[egala signo]] estas [[malbona
:<math>g(x) \in \mathcal{O}(f(x))</math>
sen diferenco en signifo. Noto ankaŭ, ke ĉi tie en
: ''O(f(x)) = g(x)''
Linio 89:
:<math>g(x) - h(x) \in \mathcal{O}(f(x))</math>
Alia anomalio de la
:<math>f(m) = \mathcal{O}(m^n)</math>
Linio 96:
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
En pli kompleksa uzado, O( ) povas aperi en malsamaj lokoj en ekvacio, eĉ kelkfoje en ĉiu flanko. Ekzemple, jeno estas vera por <math>n\to\infty</math>
Linio 104:
:<math>n^{\mathcal{O}(1)} = \mathcal{O}(e^n)</math>
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<sup>n</sup>)'' tia ke ''n<sup>f(n)</sup>=g(n)''. En terminoj de la ara
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
Linio 115:
{| class=wikitable
!
|-
| ''O(1)'' || [[Konstanto]] <br> ([[konstanta tempo]]) || Difini ĉu nombro estas para aŭ nepara
Linio 211:
* <math>o(f) \subset O(f)</math> 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
=== Aliaj ===
{| class=wikitable
! Notacio
! Priskribo
! Difino
Linio 251:
<math>\log^kn</math> estas ĉiam <math>o(n^a)</math> por ĉiu konstanto ''k'' kaj ĉiu konstanto ''a>0''.
La [[L-
:<math>L_n[\alpha, c] = O\left(e^{((c + o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha})}\right)</math>,
Linio 283:
== Eksteraj ligiloj ==
* [http://www.soe.ucsc.edu/classes/cmps102/Spring04/TantaloAsymp.pdf Enkonduko al asimptotaj
* [http://en.wikibooks.org/wiki/Data_Structures/Asymptotic_Notation#Big-O_Notation Vikilibroj] pri granda ''O''
* [[Donald Knuth]]. ''[http://doi.acm.org/10.1145/1008328.1008329 Granda Omicron kaj granda Omego kaj granda Θ]'', ACM SIGACT Novaĵoj, Volumeno 8, Eldono 2, 1976.
* [http://www.andrew.cmu.edu/~avigad/Papers/bigo.pdf Formaligo de O
* [http://www.nist.gov/dads/HTML/bigOnotation.html Granda O
* [http://www.nist.gov/dads/HTML/littleOnotation.html
* [http://www.nist.gov/dads/HTML/omegaCapital.html "Ω"]
* [http://www.nist.gov/dads/HTML/omega.html "ω"]
* [http://www.nist.gov/dads/HTML/theta.html "Θ"]
[[Kategorio:Matematika
[[Kategorio:Asimptota analitiko]]
| |||