Análisis es suavizada utiliza fuera de la academia?

Question

alisado encontrar su camino en el análisis de algoritmos corriente principal? Es común que los diseñadores de algoritmos de análisis se aplican suavizado a sus algoritmos?

Answer 1

Podría estar equivocado, pero ver el análisis suavizada como una forma de explicar el comportamiento en la práctica de algoritmos que tienen malas garantías teóricas (simplex, k-medias, etc.). No estoy seguro de lo que significaría para uso Análisis de suavizado en la práctica, excepto para justificar el uso de una heurística en particular con mal rendimiento del peor caso ( "Mi heurística tiene bla bla comportamiento peor de los casos, pero un análisis suavizado indica que se va a hacer bien en la práctica, etc, etc ")

Answer 2

La forma en que la gente a analizar algoritmos en el mundo real es muy diferente de la academia. Mientras que en el ámbito académico el objetivo es encontrar un demostrablemente-correcta límite superior en el tiempo de ejecución, en la vida real el objetivo es entender cómo funciona el algoritmo, y qué ajustes puede mejorar el tiempo de ejecución. Hay dos métodos principales que están prohibidos en el mundo académico sino que se utiliza en la práctica:

• El método de aproximación. Aquí se utiliza una gran cantidad de supuestos simplificadores para tratar de pronosticar el tiempo de ejecución de un algoritmo. De manera similar a lo que los físicos teóricos (a) utilizados hacen.
• La experimentación. El usuario ejecuta el algoritmo y medir varias estadísticas - cuánto tiempo pasó a cada parte, ¿cuántas veces se llama cada función, ¿con qué frecuencia cada ejecución rama, y ??así sucesivamente. Esta información se puede utilizar para optimizar el algoritmo. La experimentación también se utiliza para averiguar si algunas aproximaciones hechas durante el análisis de la obra algoritmo en la práctica o no.

Dicho esto, no creo que es muy común para analizar un algoritmo en la práctica, aparte de añadir un poco de texto de relleno en una publicación académica relacionada. La atención se centra tanto en la ingeniería de software o en la optimización de bajo nivel, dependiendo de la materia.

Por último, el análisis de alisado es una heurística que se puede utilizar para explicar por qué algoritmos funcionan mejor en la práctica que el peor de los casos podría sugerir - a saber, ya que algunas de las entradas son "aleatorio" en algún sentido. Esta heurística puede ser utilizado para aproximar el comportamiento del algoritmo de si se está utilizando el método de aproximación.