O (mn) é considerado crescimento "linear" ou "quadrático"?

24

Se eu tiver alguma função cuja complexidade de tempo seja O ( mn ), onde m e n são os tamanhos de suas duas entradas, chamaríamos sua complexidade de tempo de "linear" (já que é linear em m e n ) ou "quadrática" ( já que é um produto de dois tamanhos)? Ou alguma outra coisa?

Sinto que chamá-lo de "linear" é confuso porque O (m + n) também é linear, mas muito mais rápido, mas sinto que chamá-lo de "quadrático" também é estranho porque é linear em cada variável separadamente.

Mehrdad
fonte
7
É importante dizer linear em quê . Se, por exemplo, tivermos um gráfico com arestas e vértices, é linear no número de arestas, mas (potencialmente) quadrático no número de vértices. n O ( m + n )mnO(m+n)
Raphael
3
Eu acho que o comentário de Raphael está no local. "Linear" deve ser usado em relação a algo, geralmente o tamanho da entrada. Se você estiver transpondo uma matriz é "linear", pois a entrada possui o tamanho . Se você estiver procurando por ocorrências de uma cadeia de caracteres em uma cadeia de caracteres , não é linear --- seria. O ( m n ) O ( m n ) n m O ( m n ) O ( m + n )m×nO(mn)O(mn)nmO(mn)O(m+n)
SamM
3
Eu também concordaria com o comentário de @ Raphael, mas, ao mesmo tempo, não é incomum ouvir as pessoas dizerem que uma complexidade de tempo específica é "linear" sem mencionar o que é o quê. E, em alguns casos, isso não importa, por exemplo, O (m + n) é linear em relação a todas as entradas, portanto, eu não pensaria duas vezes em chamá-lo linear como SamM também fez acima. Mas isso levanta a questão: o que, se alguma coisa, torna O (mn) não linear?
Mehrdad 07/02
3
@ Mehrdad: Eu acho que a linha de base está "no tamanho da entrada, assumindo que a entrada seja codificada como string binária (em uma fita da máquina de Turing)". Este tamanho de entrada é, então, uma função de n e m em si. SamM dá bons exemplos.
Raphael
1
Veja também people.cis.ksu.edu/~rhowell/asymptotic.pdf sobre notação landau em várias variáveis.
Jonas Kölker

Respostas:

18

Em matemática, funções como essa são chamadas funções multilineares . Mas os cientistas da computação provavelmente não conhecerão essa terminologia. Esta função deve definitivamente não ser chamado linear, tanto em matemática ou ciência da computação, a menos que você pode razoavelmente considerar um dos e n uma constante.mn

Peter Shor
fonte
O que faz considerar um de e n uma constante razoável? mn
user2768
11

Para esclarecer a discussão nos comentários, é importante o que você está medindo em relação ao crescimento.

Conforme mencionado por @Kaveh, não é linear nos dois ao mesmo tempo, mas é linear se um for uma constante e o outro crescer.O(mn)

Por outro lado, provavelmente seria considerado linear. Intuitivamente, se m dobrar, ou se n dobrar, ou mesmo se m e n dobrarem, m + n não poderá mais que dobrar. Isso não é verdade para m n ; se m e n, o dobro de m n, aumenta em 4. É por isso que em muitos contextos esse tempo de execução seria considerado quadrático. Eu dou um exemplo disso com correspondência de string em alguns parágrafos.O(m+n)mnmnm+nmnmnmn

Mas geralmente quando você está usando a notação Big- , está usando-a em referência a algo em particular. Como somos na maioria teóricos, geralmente é o tamanho da entrada para o problema.O

Vamos pegar Matrix Addition, por exemplo. Adicionar duas matrizes leva tempo O ( m n ) . Mas cada elemento de nossa entrada é tocado apenas uma vez, então isso geralmente seria chamado linear. Em outras palavras, nossa entrada é do tamanho O ( m n ) , portanto, um tempo de execução de O ( m n ) é linear no tamanho da entrada.m×nO(mn)O(mn)O(mn)

Agora, vejamos a correspondência de cadeias - ou seja, recebemos uma cadeia de tamanho e uma cadeia de tamanho n e queremos ver se há uma ocorrência da cadeia menor na cadeia maior. Podemos verificar isso ingenuamente em O ( m n ) tempo; isso geralmente seria considerado quadrático. Por quê? Se m e n puder ser qualquer coisa, defina m = n . Então nosso tempo de execução é O ( m 2 ) e nossa entrada é de tamanho 2 m .mnO(mn)mnm=nO(m2)2m

Por outro lado, se usarmos o algoritmo Rabin-Karp , obtemos (em média) tempo . Nossa entrada consistia em ambas as cadeias, então nossa entrada também era do tamanho O ( m + n ) . Portanto, isso geralmente seria chamado de linear.O(m+n)O(m+n)

Resumindo: geralmente é chamado linear para coisas como multiplicação de matrizes porque é linear no tamanho da entrada, mas geralmente é chamado quadrático para coisas como correspondência de cadeias por causa da entrada menor. O termo apropriado depende do contexto em que você o está usando.O(mn)

SamM
fonte
8

Se você estiver medindo o tempo de execução em então O ( m n ) não é uma função linear em ( m , n ) . Se não houver relação entre m e n, essa função pode crescer quadraticamente em geral.(m,n)O(mn)(m,n)mn

No entanto, é uma função linear em cada um deles separadamente, ou seja, se você corrigir um deles e observar o crescimento na outra variável, será uma função linear em outro.

Kaveh
fonte
3

Para medir a complexidade dos problemas com várias entradas , uma maneira é encontrar a variável dominante e vincular outras entradas com base nessa variável. Com essa abordagem, você pode ter a função de complexidade baseada em uma única variável .

Reza
fonte
2
Pode não haver uma variável dominante, por exemplo, se você tiver o número de nós e arestas.
Raphael
0

L={w1#w2|wi(Σ{#}),}fmin{|w1|,|w2|}f(|w|)w=w1#w2LO(|w1||w2|)LO(f(|w|)(|w|f(|w|))=O(f(|w|)|w|f(|w|)2)=O(f(|w|)|w|)

O(nlogn)

frafl
fonte