algorithm - rapper - Big O al sumar diferentes rutinas
big o notation java (4)
Como dijo Ray, la respuesta es de hecho O (n log (n)). La parte interesante de esta pregunta es que no importa de qué manera lo mires: ¿agregar significa "adición real" o significa "el peor caso"? Probemos que estas dos formas de verlo producen el mismo resultado.
Sean f (n) y g (n) funciones, y sin pérdida de generalidad, supongamos que f es O (g). (Informalmente, que g es "peor" que f.) Entonces, por definición, existen constantes M y k tales que f (n) <M * g (n) siempre que n> k. Si miramos en el "peor de los casos", esperamos que f (n) + g (n) sea O (g (n)). Ahora mirándolo en la forma de "suma real", y especializándonos en el caso donde n> k, tenemos f (n) + g (n) <M * g (n) + g (n) = (M + 1 ) * g (n), y por definición f (n) + g (n) es O (g (n)) como se desee.
Digamos que tengo una rutina que escanea una lista completa de n elementos 3 veces, hace un tipo basado en el tamaño y luego busca esa lista ordenada n veces. Los escaneos son O (n) tiempo, el tipo que llamaré O (n log (n)), y el n veces bsearch es O (n log (n)). Si sumamos los 3 juntos, ¿nos da el peor caso de los 3 - el n log (n) valor (s) o la semántica permite tiempos adicionales?
Estoy bastante seguro de que, ahora que escribo esto, la respuesta es n log (n), pero podría confirmar ahora que lo tengo escrito :)
Estás en lo correcto. Cuando n se pone realmente grande, el n log (n) domina 3n.
La suma es de hecho la peor de las tres para Big-O.
La razón es que la complejidad del tiempo de su función es
(n) => 3n + nlogn + nlogn
cual es
(n) => 3n + 2nlogn
Esta función está limitada anteriormente por 3nlogn, por lo que está en O (n log n).
Puedes elegir cualquier constante. Acabo de elegir 3 porque era un buen límite superior asintótico.
Sí, será el peor de los casos, ya que la notación O solo se trata de un rendimiento asintótico.
Por supuesto, esto no debe interpretarse en el sentido de que agregar estos pasos adicionales no tendrá ningún efecto en el rendimiento de su programa. Uno de los pasos de O (n) podría consumir fácilmente una gran parte de su tiempo de ejecución para el rango dado de n donde opera su programa.