Asymptotische Analyse für zwei Variablen?

11

Wie ist die asymptotische Analyse (großes o, kleines o, großes Theta, großes Theta usw.) für Funktionen mit mehreren Variablen definiert?

Ich weiß, dass der Wikipedia-Artikel einen Abschnitt enthält, aber er verwendet viele mathematische Notationen, mit denen ich nicht vertraut bin. Ich habe auch das folgende Papier gefunden: http://people.cis.ksu.edu/~rhowell/asymptotic.pdf Das Papier ist jedoch sehr lang und bietet eine vollständige Analyse der asymptotischen Analyse, anstatt nur eine Definition zu geben. Wiederum machte es die häufige Verwendung der mathematischen Notation sehr schwer zu verstehen.

Könnte jemand eine Definition der asymptotischen Analyse ohne die komplexe mathematische Notation liefern ?

sas
quelle
1
In hohem Maße verwandt: Was bedeutet O (m + n)?
Juho

Antworten:

8

Die asymptotische Notation für multivariable Funktionen wird analog zu ihrem einzelnen variablen Gegenstück definiert. Im Fall einer einzelnen Variablen sagen wir, dass genau dann ist, wenn Konstanten C , N existieren , so dass wir für alle n > N f ( n ) C g ( n ) haben. . Mit anderen Worten, f ( n ) ist durch ein Vielfaches von g ( n ) oberbegrenzt.f(n)O(g(n))C,Nn>Nf(n)Cg(n)f(n)g(n)für alle größer als einige feste N .nN

Im multivariaten Fall ist die Definition nahezu identisch, außer dass Sie sich um einige weitere Variablen kümmern müssen. Nehmen wir an, ist eine Funktion zweier Variablen. Wir wollen f von oben durch eine andere Funktion zweier Variablen binden . Wir sagen also, dass f ( n , m ) O ( g ( n , m ) ) genau dann ist, wenn es Konstanten C , N gibt, so dass wir für alle n > N und m > N habenf(n,m)ff(n,m)O(g(n,m))C,Nn>Nm>N . Die Definition ist fast genau das gleiche, nur jetzt alle unsere Variablen größerals unsere feste Konstante sein muss N .f(n,m)Cg(n,m)N

Der Wikipedia-Artikel verwendete , um einen Vektor in R d zu bedeuten, was bedeuten würde, dass f und g multivariable Funktionen von d- Variablen sind (dh f , g : R dR ). Zu sagen, dass x i > N für alle i bedeutet, dass jede Komponente von x größer als N sein muss .xRdfgdf,g:RdRxi>NixN

Marc Khoury
quelle
2
Vielen Dank! Nur zur Bestätigung, aber ist die Definition: (1) "für alle n> N und m> N" oder (2) "für alle n> N oder m> N"? Sie und Wikipedia verwenden die Definition "und", CLRS verwendet jedoch die Definition "oder".
Sas
1
Es ist definitiv "und".
Marc Khoury