Análise assintótica para duas variáveis?

11

Como a análise assintótica (big o, little o, big theta, big theta etc.) é definida para funções com múltiplas variáveis?

Eu sei que o artigo da Wikipedia tem uma seção, mas ele usa muita notação matemática que eu não conheço. Também encontrei o seguinte artigo: http://people.cis.ksu.edu/~rhowell/asymptotic.pdf No entanto, o artigo é muito longo e fornece uma análise completa da análise assintótica, em vez de apenas fornecer uma definição. Novamente, o uso frequente de notação matemática tornou muito difícil de entender.

Alguém poderia fornecer uma definição de análise assintótica sem a notação matemática complexa?

sas
fonte
1
Altamente relacionado: Qual é o significado de O (m + n)?
Juho

Respostas:

8

A notação assintótica para funções multivariáveis ​​é definida analogamente à sua única variável equivalente. No caso de variável única, dizemos que se e somente se existirem constantes modo que, para todo , tenhamos . Em outras palavras, é delimitado por um múltiplo de para todos os maiores que alguns fixos .f(n)O(g(n))C,Nn>Nf(n)Cg(n)f(n)g(n)nN

No caso multivariado, a definição é quase a mesma, exceto que você tem mais algumas variáveis ​​para se preocupar. Vamos supor que é uma função de duas variáveis. Queremos vincular de cima por outra função de duas variáveis. Então dizemos que se e somente se existir constantes modo que, para todo e , tenhamos . A definição é quase exatamente a mesma, exceto que agora todas as nossas variáveis ​​devem ser maiores que a constante fixa .f(n,m)ff(n,m)O(g(n,m))C,Nn>Nm>Nf(n,m)Cg(n,m)N

O artigo da wikipedia usou para significar um vetor em que significaria que e eram funções multivariáveis ​​de variáveis (ou seja ). Dizendo que para todos significava que cada componente do tinha que ser maior do que . Rdfgdf,g:RdRxi>NiX NxRdfgdf,g:RdRxi>NixN

Marc Khoury
fonte
2
Obrigado! Apenas confirmando, mas é a definição: (1) "para todos n> N e m> N" ou (2) "para todos os n> N ou m> N"? Você e a Wikipedia usam a definição "e", no entanto, o CLRS usa a definição "ou".
sas
1
É definitivamente "e".
21412 Marc