Falta un paso importante en su análisis, es cómo está realizando el análisis. Cuando generalmente analizamos un algoritmo, generalmente observamos la situación del peor de los casos , pero también es apropiado considerar la situación del caso promedio . Estos se denominan ” análisis del peor de los casos ” y ” análisis del caso promedio “, respectivamente. Cuando no determina el tipo de análisis que está realizando, no queda claro qué está analizando, porque un algoritmo hará diferentes cosas en situaciones particulares.
La peor de las situaciones es cuando el elemento no se encuentra en la matriz (o se mira el último elemento). Esto significa que tiene que repetir [math] \ Theta (n) [/ math] veces para determinar esto. Es por eso que decimos que la búsqueda lineal requiere [matemática] \ Theta (n) [/ matemática] en el peor de los casos (o que su complejidad temporal es lineal). El beneficio del análisis del peor de los casos es que usted sabe que el algoritmo no se ejecutará por más tiempo que el peor de los casos, por lo que su rendimiento no será peor que esto.
Esta también es una oportunidad para señalar que los asintóticos no son exclusivos de los tipos de análisis (peor, promedio, mejor). Es un límite asintótico. Por ejemplo, podría expresar un análisis de caso promedio en términos de Big-Theta, Big-Oh o Big-Omega. Big-Theta es el que debe luchar porque es asintóticamente ajustado, aunque la mayoría de la gente escribe Big-Oh de todos modos para decir esto (aunque en teoría no tiene por qué ser lo mismo, porque el análisis puede no ser estricto).
- ¿Cuáles son algunos de los algoritmos comunes y estrategias de diseño utilizados por los desarrolladores de juegos sin fin?
- ¿Cuál es la diferencia entre el algoritmo memético y el algoritmo genético?
- ¿Qué factores consideraría al crear un algoritmo para predecir cuándo los propietarios pondrán su casa en el mercado?
- ¿Cuáles son los factores que afectan la tasa de error en el algoritmo KNN?
- ¿Qué es un contador Loglog?
Ahora a la pregunta en su título: Esto dependería de qué definición de algoritmo esté usando. Muchos consideran que un algoritmo es un procedimiento paso a paso finito e inequívoco que toma una instancia de entrada para producir una salida para una instancia dada de un problema. Sinceramente, no sé si podría (aún una pregunta interesante), porque los investigadores estudian activamente los límites de los algoritmos (por ejemplo, cuando un límite en el tiempo de ejecución de un algoritmo no es nítido porque el algoritmo es muy sofisticado, algunos ejemplos en el pasado incluye el método simplex). Además, es posible crear funciones de crecimiento que no comparten los mismos resultados Big-Oh y Big-Omega. Por ejemplo, uno puede crear una función de crecimiento por partes (¿cada algoritmo tiene Big Omega?). Dan un ejemplo simple donde un límite Big-Theta no existe para una función de crecimiento. Es decir, sea [matemática] f (n) = 1 [/ matemática] si [matemática] n [/ matemática] es impar y [matemática] f (n) = n [/ matemática] si [matemática] n [/ matemática ] incluso. Observe que es [matemáticas] \ Omega (1) [/ matemáticas] y [matemáticas] O (n) [/ matemáticas]. No se puede decir para esta función de crecimiento que es [matemática] \ Omega (n) [/ matemática] porque no se vincula desde abajo del caso cuando [matemática] n [/ matemática] es impar. (Editar: por supuesto, puede decir que es [matemáticas] \ Theta (f (n)) [/ matemáticas], pero eso no nos lleva a ninguna parte realmente, ya que queremos capturar su complejidad en términos del tamaño de entrada). El crecimiento La función está formulada por el tipo de análisis que realiza, por lo que esa pregunta es mucho más complicada.
Ahora, si su pregunta es si en todos los casos de análisis puede encontrar un límite Big-Theta para el análisis. Estoy seguro de que la respuesta es no. Esto no es difícil de ver. Por ejemplo, la búsqueda lineal en el análisis del mejor caso toma [math] \ Theta (1) [/ math], mientras que en el análisis del peor caso toma [math] \ Theta (n) [/ math].
Esto ¿Puede expresarse el tiempo de ejecución de cada algoritmo como $ \ Theta (f (n)) $? También ofrece una discusión sobre esto, aunque creo que es vital que las personas hagan la distinción sobre qué tipo de análisis están realizando porque Es un malentendido común en el análisis de algoritmos (generalmente por estudiantes universitarios) para asociar cada uno con un tipo de análisis exclusivamente, cuando no es el caso.
¡Espero que esto ayude!
