¿Puede una complejidad de tiempo Big-Oh contener más de una variable?

Digamos, por ejemplo, que estoy procesando cadenas que requieren un análisis de dos cadenas. No he dado información sobre cuáles podrían ser sus longitudes, por lo que provienen de dos familias distintas. ¿Sería aceptable llamar a la complejidad de un algoritmo u (dependiendo de si usamos un algoritmo ingenuo u optimizado)?O ( n + m $O(n * m)$$O(n + m)$

En una línea similar, supongamos que el algoritmo que elegimos realmente requiere dos etapas: una fase de configuración en la primera cadena que nos permite procesar cualquier número de otras cadenas sin incurrir en ese costo inicial. ¿Se consideraría apropiado decir que tiene una construcción seguida de cualquier número de cálculos de ?O ( m $O(n)$$O(m)$

¿Sería apropiado simplemente llamarlos porque ambos cálculos son lineales?$O(n)$

Sí, por supuesto. Esto está bien y es perfectamente aceptable. Es común y estándar ver algoritmos cuyo tiempo de ejecución depende de dos parámetros.

Por ejemplo, a menudo verá el tiempo de ejecución de la búsqueda de profundidad primero expresada como , donde n es el número de vértices ym es el número de aristas en el gráfico. Esto es perfectamente válido. El significado de esto es que existe una constante c y números n 0 , m 0, de modo que el tiempo de ejecución del algoritmo es como máximo c ⋅ ( n + m ) , para todos n > n 0 , m > m $O(n+m)$$n$$m$$c$$n_0,m_0$$c \cdot (n+m)$$n>n_0,m>m_0$. En otras palabras, si el tiempo de ejecución exacto es , decimos que f ( n , m ) = O ( n + m ) si existe c , n 0 , m 0 tal que n > n 0 y m > m 0 implica f ( n , m ) ≤ c ⋅ ( n + m $f(n,m)$$f(n,m) = O(n+m)$$c,n_0,m_0$$n>n_0$$m>m_0$$f(n,m) \le c \cdot (n+m)$.

Sí, es perfectamente apropiado y aceptable decir que la primera etapa toma tiempo y la segunda etapa toma tiempo O ( m ) .$O(n)$$O(m)$

Importante: asegúrese de definir qué son y m . No puede decir "este es un algoritmo de tiempo O ( n ) " sin especificar qué es n . Si n no se especifica en el enunciado del problema, debe especificarlo. Por ejemplo, vea algoritmos de gráficos, donde generalmente definimos n = # de vértices ym = # de aristas.$n$$m$$O(n)$$n$$n$$n =$$m =$

En cuanto a si puede llamarlos tiempo , no, por supuesto que no, a menos que de alguna manera sepa que m = O ( n ) . Por supuesto, si sabe que m = O ( n ) , entonces se deduce que m + n = O ( n ) , por lo que un algoritmo de tiempo O ( m + n ) también es un algoritmo de tiempo O ( n ) . Pero si no hay garantía de que m = O $O(n)$$m = O(n)$$m = O(n)$$m+n = O(n)$$O(m+n)$$O(n)$ , entonces no puede llamarlo unalgoritmo de tiempo O ( n ) .$m = O(n)$$O(n)$

Esto es algo básico. Lo encontrarás en todos los algoritmos de los libros de texto.