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

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.

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.$m$$n$

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 $O(m+n)$$m$$n$$m$$n$$m+n$$mn$$m$$n$$mn$

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\times n$$O(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 .$m$$n$$O(mn)$$m$$n$$m = n$$O(m^2)$$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)$

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)$$m$$n$

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.

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 .

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 = \{w_1\#w_2|w_i \in (\Sigma\setminus\{\#\})^*,\dots\}$$f$$\min\{|w_1|,|w_2|\} \leq f(|w|)$$w=w_1\#w_2 \in L$L O ( f ( | w | ) ⋅ ( | w | - f ( | w | ) ) = O ( f ( | w | ) | w | - f ( | w | ) 2 ) = O ( f ( | w | ) | w |$\mathcal O(|w_1|\cdot|w_2|)$$L$$\mathcal O(f(|w|)\cdot(|w|-f(|w|))= \mathcal O(f(|w|)|w|-f(|w|)^2)= \mathcal 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.$\mathcal O(n\log n)$