¿Regla de suma para BIG-O con funciones iguales de complejidad?

Question

Una propiedad de la Notación BIG-O-Notación es la la regla de suma , que afirma que cuando tengo dos funciones $ f_1 $ y $ f_2 $ y sus funciones de complejidad correspondientes son $ G_1 $ y $ g_2 $ , entonces la complejidad combinada es $ F_1 + F_2= O (\ MAX (G_1, G_2)) $ .

¿Pero qué elegimos si ambas funciones de complejidad son iguales? Por ejemplo, si $ f_1 (n) $ es la clasificación de una matriz y $ _ f2 (m) $ Además, las complejidades son $ O (n \ log (n)) $ y $ o (M \ log ( m)) $ . La aplicación de la regla sería $ O (\ max (n \ log (n), m \ log (m))) $ . Creo que elegir cualquiera de ellos cedería una estimación válida pero muy intuitiva, ya que abandonaría una variable. Además de eso, no está claro cuál elegir.

¿Es el caso que no se supone que use la regla cuando hay varias variables involucradas?

Answer 1

Depende de si algunas variables dependientes de otra, o si se les da como parámetros en el problema. Por ejemplo, en muchos problemas relacionados con el gráfico, $ n $ puede ser el número de vértices, y $ m $ Puede ser el número de bordes. En este caso, $ m $ puede ser tan grande como $ o (n ^ 2) $ . Así, en el caso general, digamos si tenemos un algoritmo cuya primera fase se ejecuta en $ o (n) $ y la segunda fase se ejecuta en $ O (m) $ , simplemente agregamos los dos términos juntos y no intentamos simplificar --- El tiempo final final es $ O (n + m) $ .

En términos de varias variables dadas como parámetros que no están necesariamente relacionados: se une las variables múltiples dentro de la ecuación final, por ejemplo, por ejemplo. Puedo decir que multiplicar un $ m \ veces n $ matrix y un $ n \ veces p $ matrix Toma $ O (MNP) $ -time usando la multiplicación de la escuela de escuela, o resolviendo el problema de Knapsack toma $ O (nt) $ < / span> -time donde $ n $ es el número de elementos y $ t $ es la suma objetivo .

En casos especiales como gráficos planares y otros gráficos escasos, sabemos que $ m= o (n) $ , para que podamos sustituir con seguridad $ n $ en lugar de $ m $ en el tiempo final de ejecución para la simplificación.

Como digresión, esto ilustra por qué en gráficos escasos (donde $ m= o (n) $ ), uno preferiría usar DIJKTRA en un bucle para todos- pares de ruta más corta (en contraste con un algoritmo basado en el cierre transitivo como Floyd-Warshall); Dado que ahora se ejecuta Dijkstra en $ o (m \ log n)= O (n \ log n) $ , la complejidad general para usar Dijkstra en un bucle se convierte en $ O (n ^ 2 \ log n) $ , que es mejor que Floyd-Warshall. Por el contrario, tenga en cuenta que las carreras de Dijkstra en $ m \ log n $ para el caso general, lo que significa en gráficos densos donde $ m= O (n ^ 2) $ , se vuelve menos eficiente que Floyd-Warshall en términos del tiempo de funcionamiento en el peor de los casos.

En otros casos, puede haber variables ni siquiera se limitan a polinomialmente por un parámetro dado, tome el ejemplo de Knapsack anterior, donde $ t $ puede ser exponencial en $ n $ .

Answer 2

No hay respuesta general.Por cierto, si desea simplificar el $ o (\ max (n \ log (n), m \ log (m))) $ , puede reescribircomo $ o ((n + m) \ log (n + m)) $ .

Además, si $ g_1 $ y $ g_2 $ son eqaul y funcionamiento creciente, puedes escribir $ o (g_1 (n + m)) $ en lugar de $ o (\ max (g_1 (n), g_2 (m))) $ .

Answer 3

por definición $ o (g) $ debe ser siempre definido variable y el punto de límite con respecto al considerar $ o $ . Por ejemplo, en $ o (n ^ 3), n \ a \ infortes $ variable es $ n $ y el punto de límite $ \ infty $ . En $ O (x ^ 3), x \ a 0 $ variable es $ x $ y límite punto $ 0 $ .

Entonces, cuando escribimos $ f= o (g) $ , entonces formalmente nos referimos a una variable y algún punto límite. Por ejemplo, $ f (n)= o (g (n)), n \ a \ inforty $ es un registro exacto. Tenga en cuenta, que registro $ f (m)= O (g (m)), m \ a \ infty $ significa exactamente lo mismo que frase anterior.

Cuando estamos hablando de la propiedad $ f_1 + f_2= o (\ max (g_1, g_2)) $ , entonces, aquí también se debe indicar cierta variable (s ) y algún punto de límite. Así que el registro exacto debe ser algo así $$ F_1 (N) + F_2 (N)= O (\ MAX (G_1, G_2) (N)), N \ a \ INFTY $$ O necesitamos más aclaraciones con respecto a las variables, asumiendo el punto de límite $ \ INFTY $ .