O (log N) == O (1) - ¿Por qué no?
Cuando considero los algoritmos / estructuras de datos, tiendo a reemplazar las partes del registro (N) por constantes. Oh, ya sé que log (N) diverge, pero ¿importa en aplicaciones del mundo real?
log (infinito) <100 para todos los propósitos prácticos.
Tengo mucha curiosidad por los ejemplos del mundo real donde esto no se cumple.
Para aclarar:
Entiendo O (f (N))Tengo curiosidad por los ejemplos del mundo real donde elasintótico el comportamiento importa más que elconstantes de la actuación real.Si log (N) puede reemplazarse por una constante, todavía puede reemplazarse por una constante en O (N log N).Esta pregunta es por el bien de (a) entretenimiento y (b) para reunir argumentos para usar si me encuentro (nuevamente) en una controversia sobre el rendimiento de un diseño.