Si eres un ingeniero de software, probablemente no sea tan útil, una vez que vayas más allá de lo básico. Las consideraciones prácticas finalmente importan más que el análisis big-O. Eso no quiere decir que big-O no importe: un algoritmo de tiempo lineal generalmente superará a un algoritmo de tiempo cuadrático en casos del tamaño del mundo real. Le ayuda a clasificar los algoritmos en “eficiente” frente a “ineficiente”. Pero hay una gran diferencia entre 1000n yn que importa en términos prácticos. Big-O es “regla de oro”, no “muy útil”.
¿Por qué se usa la clasificación rápida cuando es O (n ^ 2), en comparación con la O del montón (n log n)? Porque generalmente es más rápido, en un múltiplo de 2–3, en comparación con una implementación de montón construida con la misma tecnología.
¿Por qué usar Timsort en lugar de un montón genérico? Porque los datos del mundo real, que a menudo ya están ordenados parcialmente, funcionan mejor en Timsort. No es un análisis que el análisis big-O te dará.
- ¿Qué sitios web o aplicaciones usan el algoritmo de correspondencia para el cual los profesores Roth y Shapley ganaron el Premio Nobel en 2012?
- ¿Cuál es el algoritmo euclidiano para encontrar GCD? ¿Es un algoritmo tan bueno en términos de rendimiento y análisis de tiempo de ejecución?
- ¿Es necesario codificar todos los datos en estructuras como pilas en C ++, o es un conocimiento práctico suficiente para aclarar entrevistas?
- Noruega: ¿Cómo funciona BankID?
- ¿Hay algún libro para la recursividad?
¿Estás operando en una máquina Turing? Probablemente no, probablemente esté ejecutando en una máquina de acceso aleatorio con una jerarquía de memoria (caché L1, caché L2, memoria principal, almacenamiento de respaldo). Y el comportamiento de la jerarquía de memoria es muy importante en el rendimiento práctico.
Si usted es un científico de la computación teórico, big-O (y sus primos) le brindan una manera de hablar sobre el desempeño del algoritmo de manera matemática, lo que resume los detalles de una máquina en particular. Nuevamente, para casos simples, generalmente es cierto que mejores límites en teoría también se traducen en mejores límites en la práctica. Y si va a comparar dos algoritmos, el comportamiento asintótico es sin duda uno de los puntos de referencia más obvios y útiles. Pero a menudo los mejores límites teóricos vienen con una implementación que es más lenta en todos los tamaños excepto en los “galácticos”. ¡Muchos algoritmos nuevos nunca se implementan en absoluto! El análisis asintótico permite la discusión de algoritmos como objetos matemáticos en lugar de artefactos prácticos. (Algunos investigadores prefieren los recuentos exactos de las operaciones, si se pueden lograr, en lugar de solo el límite asintótico, por ejemplo, “2n ^ 2 + 3n multiplicaciones” en lugar de solo “O (n ^ 2) multiplicaciones”).
Ver ¿Qué es un algoritmo galáctico?
