Analiza asymptotyczna dla dwóch zmiennych?

11

Jak definiuje się analizę asymptotyczną (duża o, mała o, duża theta, duża theta itp.) Dla funkcji z wieloma zmiennymi?

Wiem, że artykuł w Wikipedii zawiera sekcję, ale wykorzystuje wiele notacji matematycznych, których nie znam. Znalazłem również następujący artykuł: http://people.cis.ksu.edu/~rhowell/asymptotic.pdf Jednak artykuł jest bardzo długi i zawiera pełną analizę analizy asymptotycznej, a nie tylko definicję. Ponownie częste stosowanie notacji matematycznej bardzo utrudniało zrozumienie.

Czy ktoś mógłby podać definicję analizy asymptotycznej bez złożonej notacji matematycznej?

sas
źródło
1
Wysoce powiązane: Jakie jest znaczenie O (m + n)?
Juho,

Odpowiedzi:

8

Notacja asymptotyczna dla funkcji wielu zmiennych jest definiowana analogicznie do jej pojedynczego zmiennego odpowiednika. W przypadku pojedynczej zmiennej mówimy, że wtedy i tylko wtedy, gdy istnieją stałe C , N takie, że dla wszystkich n > N mamy f ( n ) C g ( n ) . Innymi słowy f ( n ) jest górne ograniczone pewną wielokrotnością g ( n )f(n)O(g(n))C,Nn>Nf(n)Cg(n)f(n)g(n)dla wszystkich większe niż pewnej ustalonej N .nN

W przypadku wielowymiarowym definicja jest prawie taka sama, z tym wyjątkiem, że musisz się martwić o kilka zmiennych. Załóżmy, że jest funkcją dwóch zmiennych. Chcemy związać f od góry inną funkcją dwóch zmiennych. Mówimy więc, że f ( n , m ) O ( g ( n , m ) ) wtedy i tylko wtedy, gdy istnieją stałe C , N takie, że dla wszystkich n > N i m > N mamyf(n,m)ff(n,m)O(g(n,m))C,Nn>Nm>N . Definicja ta jest niemal dokładnie takie same, z wyjątkiem teraz wszystkich naszych zmiennych musi być większa niż nasze ustalonej stałej N .f(n,m)Cg(n,m)N

Artykuł w Wikipedii użył aby oznaczać wektor w R d, co oznaczałoby, że f i g były wielowymiarowymi funkcjami zmiennych d (tj. F , g : R dR ). Mówiąc, że x i > N dla wszystkich I oznacza, że każdy składnik x musi być większa niż N .xRdfgdfa,sol:RreRxja>N.jaxN.

Marc Khoury
źródło
2
Dzięki! Tylko potwierdzenie, ale czy definicja: (1) „dla wszystkich n> N i m> N” lub (2) „dla wszystkich n> N lub m> N”? Ty i Wikipedia korzystacie z definicji „i”, jednak CLRS używa definicji „lub”.
sas
1
To zdecydowanie „i”.
Marc Khoury,