Tendría una pregunta bastante general. ¿Alguna vez ha tenido que calcular realmente (por ejemplo, en el papel) la complejidad de un algoritmo, excepto en la escuela como programador? Y si ... ¿puedes darme un ejemplo, por favor?complejidad del algoritmo
ti :) gracias
No sé si se tiene en cuenta concursos de programación como la escuela o no, pero a ver si se puede resolver un problema de competencia (con las limitaciones de tamaño problema especificados) en el límite de tiempo, debe estimar aproximadamente el número de operaciones considerando la complejidad del algoritmo utilizado.
Si está escribiendo un software y puede pensar en múltiples formas de implementarlo, a menudo uno de los factores decisivos (además de la complejidad conceptual y el tiempo para implementarlo) será la complejidad algorítmica. Por lo tanto, cuando su jefe quiere una justificación para su decisión, es necesario descubrir la complejidad de cada uno. Mientras que algunos pueden considerar esto una forma de optimización prematura, creo que el consenso es que elegir un diseño apropiado para su problema es solo una buena ingeniería de software.
En el trabajo, casualmente discutimos la variación de algoritmos para resolver un problema y la complejidad desempeña su papel. Nunca es algo en lo que tenemos que hacer pruebas rigurosas de complejidad, sino solo un general "podríamos hacer X, pero eso sería O (N^2) que es demasiado porque podríamos iterar sobre millones de filas".
La optimización excesiva puede generar código incorrecto, pero conocer la complejidad de su algoritmo básico ayuda mucho a determinar la mejor manera de resolver un problema de programación.
¡Por supuesto! En cualquier momento, estás haciendo algo más de un millón de veces, es posible que quieras verificar tu algoritmo.
Una instancia que hice fue cuando estaba generando millones de imágenes que tenían que caber en un patrón de cuadrícula. Lo siento, no puedo ser mucho más específico para eso.
Absolutamente, recientemente tuvimos un problema con nuestra aplicación donde de repente comenzó a experimentar algunas ralentizaciones importantes. Resultó que teníamos un algoritmo cúbico (O (n^3)) justo en el medio de una función muy importante. Se había escondido bajo capas de abstracción. Averiguar lo que había sucedido requería trazar el gráfico de llamadas de función y observar los detalles.
Es cierto que una vez que lo hicimos, no es como si tuviera que aplicar matemática para notar un algoritmo O (n^3), pero eso es principalmente porque 3 años de Análisis de Algoritmos en la universidad me han dado una sensación general cómo es un algoritmo cúbico
De todos modos, resultó que N había aumentado un poco, pero estaba a punto de pasar de unos pocos cientos de milisegundos a unos segundos y luego a unos minutos, por lo que el problema no se había demostrado hasta hace poco.
En la mayoría de los casos, utilizará algoritmos preempaquetados que tienen complejidades definidas. Quicksort es O (n^2) el peor caso y O (n * log (n)) promedio de casos, la búsqueda binaria es O (log (n)), etc. Las bibliotecas generalmente especificarán cuáles son sus características de rendimiento, y usted solo tiene que preocuparse por cómo se componen.
Sí.
En general, la complejidad es lo suficientemente obvia como para adivinar servilletas, y eso está bien para el desarrollo hasta que llegue el momento en que necesito medir el rendimiento. En muchos casos, la sección que me preocupaba estaba bien (es decir, la conjetura de la servilleta era lo suficientemente buena) y algo más está desacelerando el software. En casi todos los casos vale la pena seguir mis suposiciones básicas y medir el rendimiento más adelante.
Sin embargo, cuando estoy haciendo mucho tiempo código crítico, especialmente en procesamiento de gráficos, me siento y determinar la complejidad del algoritmo y compensaciones asociada a hacerlo de una manera alternativa.
Hoy estoy trabajando con alguien código de otra persona y es terriblemente lento. Realmente no me importa, puede tomar 10 minutos para todo lo que importa para el proceso general que mejora. Pero tuve que mirar el código para corregir un error, y esta persona tiene bucles dentro de los bucles dentro de los bucles, la mayoría de ellos busca la misma lista de la misma manera para un elemento diferente cada vez. En esencia ha cambiado un buen arrayfunction, dicen func (i) {devuelve registros [i];} en una rutina de búsqueda horribles:
func(i)
{
for each index in records
if i==index return records[index]
next
}
la realidad es mucho peor, pero se entiende la idea.
La razón por la que está aprendiendo esto en la escuela actual es: para que pueda ver estas estructuras y clasificar automáticamente. Es probable que no necesite realmente computarizar o reducirlo a un buen número de complejidad ordenada, pero si no lo hace ahora a mano y lo ve mucho, también producirá un código así y usted simplemente no tener idea.
-Adam
No sé que en realidad escribir las cosas, pero todo el tiempo evalúo cómo estoy construyendo mis algoritmos para ver si puedo mejorar la eficiencia de la misma. Para el código me pregunto si hay una manera de convertir bucles anidados en un solo bucle o de un bucle a usar un enfoque de dividir y conquistar. Esto sería equivalente a pasar de O (N) a O (N) y O (N) a O (log N). Lo mismo es cierto de SQL - puedo eliminar una combinación y hacer una subconsulta en lugar de utilizar un índice - tal vez va de O (N 2 ) a O (N) (o incluso O (1) si se me permite indexados consultas en ambas tablas).
Sí y no.
estaba escribiendo una herramienta para aplanar dependencias RPM de un conjunto de paquetes en una sola cadena. La solución obvia corría demasiado despacio, así que busqué en mi memoria un poco para recordar un algoritmo O(n+m) de la clase de teoría de gráficos. Hice un poco de cálculo de back-of-the-sobre para asegurarse de que realmente era O(n+m), luego escribió y ponerlo en producción :)
tienes un ejemplo de SQL que usted menciona? porque las combinaciones con índices y subconsultas son más o menos equivalentes (a menudo uno se implementa con el otro) – Javier
No estaba pensando realmente en un ejemplo en particular, solo en el proceso general. – tvanfosson
Con SQL podría ser tan simple como darse cuenta de que agregar un índice le permitiría usar un algoritmo diferente que sería más eficiente. – tvanfosson