Hola!
Quería saber bajo qué hipótesis de n y m se pueden comparar órdenes. Es decir, cuándo puedo decir que un algoritmo que es O(m+n) y O(n)? , o cuándo un algoritmo es O(n) y O(m.log n)?
Gracias!
hola Nicolás,
no se si entendí bien así que no estoy seguro que lo siguiente sea de utilidad.
el tiempo de ejecución de un algoritmo se expresa en función del tamaño de la entrada. entonces, si decimos que el tiempo de ejecución T(m+n) = O(m+n) significa que la velocidad de crecimiento del tiempo de ejecución respecto al tamaño de la entrada es constante o que el tiempo de ejecución es proporcional al tamaño de la entrada. si en este caso, además dijéramos que T(m+n) = O(n), y estamos hablando de que la entrada es un grafo, diría que el tiempo invertido por el algoritmo no depende de la cantidad de aristas aunque eso no tiene ninguna implicación sobre n y m.
por otro lado, es importante recordar que este análisis se realiza justamente para
ciertos "escenarios" (peor, mejor o caso promedio que definen familias de
instancias) donde se espera que el algoritmo deba realizar el máximo,
mínimo o un esfuerzo medio, respectivamente. entonces, es considerando estos casos que sería correcto imponer una relación entre m y n. p.e.
en grafos completos, la cantidad de aristas m=n^2 podría hacer que el
esfuerzo de algunos algoritmos esté más concentrado en el procesamiento de las
aristas o, en el caso de un grafo más disperso o menos conectado, más
concentrado en el procesamiento de los vértices.
algo parecido podría analizarse para la relación entre O(n) y O(mlgn) pero habría que saber de qué algoritmos hablamos.
saludos