Esta es una pregunta básica, pero estoy pensando que es lo mismo que , ya que el término más grande debería dominar a medida que avanzamos hasta el infinito. Además, eso sería diferente de O (\ min (m, n)) . ¿Está bien? Sigo viendo esta notación, especialmente cuando discuto algoritmos gráficos. Por ejemplo, usted ve habitualmente: O (| V | + | E |) (por ejemplo, vea aquí ).
44
Respuestas:
Tienes razón. Observe que el términoO(n+m) abusa levemente de la notación clásica big-O , que se define para funciones en una variable. Sin embargo, existe una extensión natural para múltiples variables.
Simplemente hablando, dado que
Por otro lado,O(n+m) es diferente de O(min{n,m}) , ya que si establece n=2m , obtendrá
fuente
Lo creas o no, parece (en mi experiencia) que muchos algoritmos la gente realmente no ha pensado en lo que significa formalmente la gran notación O, y cuando se le pregunta al respecto, puede obtener varias respuestas diferentes. Algunos temas se discuten en el documento sobre la notación asintótica con múltiples variables de Rodney R. Howell.
Curiosamente, también parece que la mayoría de los cursos de algoritmos introductorios pasan mucho tiempo siendo muy formales acerca de la notación O grande con una sola variable, y luego las próximas semanas usan felizmente la notación para algoritmos gráficos con varias variables de una manera informal, sin discutir qué notación realmente significa.
fuente