¿Se considera O (mn) crecimiento "lineal" o "cuadrático"?

24

Si tengo alguna función por su complejidad, el tiempo es O ( mn ), donde m y n son los tamaños de sus dos entradas, tendría que llamar a su complejidad tiempo "lineal" (ya que es lineal en ambos m y n ) o "cuadrática" ( ya que es un producto de dos tamaños) ¿O algo mas?

Siento que llamarlo "lineal" es confuso porque O (m + n) también es lineal pero mucho más rápido, pero siento que llamarlo "cuadrático" también es extraño porque es lineal en cada variable por separado.

Mehrdad
fuente
77
Es importante decir lineal en qué . Si, por ejemplo, tenemos un gráfico con aristas vértices, es lineal en el número de aristas, pero (potencialmente) cuadrático en el número de vértices. n O ( m + n )mnO(m+n)
Raphael
3
Creo que el comentario de Raphael es acertado. "Lineal" debe usarse en relación con algo, a menudo el tamaño de la entrada. Si está transponiendo una matriz , es "lineal" ya que la entrada tiene un tamaño . Si está buscando ocurrencias de una cadena de caracteres en una cadena de caracteres , no es lineal --- lo sería. 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
También estaría de acuerdo con el comentario de @ Raphael, pero al mismo tiempo no es raro escuchar a la gente decir que una complejidad de tiempo particular es "lineal" sin mencionar en relación a qué. Y en algunos casos no importa, por ejemplo, O (m + n) es lineal en relación con todas las entradas, por lo que no lo pensaría dos veces antes de llamarlo lineal como SamM también hizo anteriormente. Pero eso plantea la pregunta: ¿qué hace que O (mn) no sea lineal?
Mehrdad
3
@Mehrdad: Creo que la línea de base está "en el tamaño de entrada, suponiendo que la entrada esté codificada como una cadena binaria (en una cinta de máquina de Turing)". Este tamaño de entrada es entonces una función de y . SamM da buenos ejemplos. mnm
Raphael
1
Ver también people.cis.ksu.edu/~rhowell/asymptotic.pdf sobre notación de landau en múltiples variables.
Jonas Kölker

Respuestas:

18

En matemáticas, funciones como esta se llaman funciones multilineales . Pero los informáticos probablemente no conocerán esta terminología en general. Esta función debe sin duda no será llamado lineal, ya sea en matemáticas o ciencias de la computación, a menos que se puede considerar razonablemente uno de y una constante.nmn

Peter Shor
fuente
Lo que hace considerando uno de y un razonable constante? nmn
user2768
11

Para dilucidar la discusión en los comentarios, importa a qué se esté midiendo el crecimiento en relación.

Como mencionó @Kaveh, no es lineal en ambos al mismo tiempo, pero es lineal si uno es constante y el otro crece.O(mn)

Por otro lado, probablemente se consideraría lineal. Intuitivamente, si duplica, o si duplica, o incluso si y duplican, no puede ser más del doble. Esto no es cierto para ; si y tanto doble sube por 4. Por esta razón, en muchos contextos esto Duración sería considerado cuadrática. Doy un ejemplo de esto con la coincidencia de cadenas en un par de párrafos.m n m n m + n m n m n m nO(m+n)mnmnm+nmnmnmn

Pero, por lo general, cuando usa la notación Big- , la usa en referencia a algo en particular. Como somos principalmente teóricos, generalmente es el tamaño de la entrada al problema.O

Tomemos Matrix Addition, por ejemplo. Agregar dos matrices toma tiempo. Pero cada elemento de nuestra entrada solo se toca una vez, por lo que esto generalmente se llamaría lineal. En otras palabras, nuestra entrada es de tamaño , por lo que un tiempo de ejecución de es lineal en el tamaño de la entrada.m×nO(mn)O(mn)O(mn)

Ahora veamos la coincidencia de cadenas, es decir, se nos da una cadena de tamaño una cadena de tamaño queremos ver si hay una cadena más pequeña dentro de la cadena más grande. Podemos comprobar esto ingenuamente en tiempo ; esto generalmente se consideraría cuadrático. ¿Por qué? Si y pueden ser cualquier cosa, set . Entonces nuestro tiempo de ejecución es y nuestra entrada es de tamaño .mnO(mn)mnm=nO(m2)2m

Por otro lado, si usamos el algoritmo Rabin-Karp , obtenemos (en promedio) tiempo . Nuestra entrada consistía en ambas cadenas, por lo que nuestra entrada también era de tamaño . Por lo tanto, esto generalmente se denominaría lineal.O(m+n)O(m+n)

Para resumir: generalmente se llama lineal para cosas como la multiplicación de matrices porque es lineal en el tamaño de la entrada, pero generalmente se llama cuadrático para cosas como la coincidencia de cadenas debido a la entrada más pequeña. El término apropiado depende del contexto en el que lo esté utilizando.O(mn)

SamM
fuente
8

Si está midiendo el tiempo de ejecución en entonces no es una función lineal en . Si no existe una relación entre y esta función puede crecer quadraticly en general.(m,n)O(mn)(m,n)mn

Sin embargo, es una función lineal en cada una de ellas por separado, es decir, si arregla una de ellas y observa el crecimiento en la otra variable, entonces es una función lineal en la otra.

Kaveh
fuente
3

Para medir la complejidad de los problemas con múltiples entradas , una forma es encontrar la variable dominante y luego vincular otras entradas basadas en esa variable. Con este enfoque, podría tener la función de complejidad basada en una sola variable .

Reza
fuente
2
Es posible que no haya una variable dominante, por ejemplo, si tiene el número de nodos y aristas.
Raphael
0

Dado un idioma y una función tal que para cada puede estimar el tiempo de ejecución de un algoritmo que reconoce como .L={w1#w2|wi(Σ{#}),}fmin{|w1|,|w2|}f(|w|)w=w1#w2LL O ( f ( | w | ) ( | w | - f ( | w | ) ) = O ( f ( | w | ) | w | - f ( | w | ) 2 ) = O ( f ( | w | ) | w | )O(|w1||w2|)LO(f(|w|)(|w|f(|w|))=O(f(|w|)|w|f(|w|)2)=O(f(|w|)|w|)

Esto significa que obtienes tiempo lineal, si la parte más pequeña de tu entrada es constante (en relación con la entrada completa), algo intermedio (como ) si es tiempo de ejecución sublineal y cuadrático si es lineal.O(nlogn)

frafl
fuente