¿Es programático encontrar la notación Landau (notación Big O o Theta) de un algoritmo?

12

Estoy acostumbrado a buscar la notación Landau (Big O, Theta ...) de mis algoritmos a mano para asegurarme de que estén lo más optimizados posible, pero cuando las funciones son realmente grandes y complejas, está tomando demasiado tiempo para hacerlo a mano. también es propenso a errores humanos.

Pasé un tiempo en Codility (ejercicios de codificación / algo), y me di cuenta de que te darán la notación de Landau para tu solución enviada (tanto en el uso de Tiempo como de Memoria).

Me preguntaba cómo hacen eso ... ¿Cómo lo harías?

¿Hay otra forma además del análisis léxico o el análisis del código?

Esta pregunta se refiere principalmente a PHP y / o JavaScript, pero estoy abierto a cualquier lenguaje y teoría.

    
pregunta Julien L 07.09.2012 - 04:33

5 respuestas

12
  

Me preguntaba cómo lo hacen ... ¿Cómo lo harías?

Imagino que en realidad están estimando las medidas de Big O ... ejecutando el programa para diferentes tamaños de problemas, midiendo el tiempo y el uso del espacio, y ajustando curvas a los resultados.

El problema con este enfoque es que puede hacerlo mal si las funciones de costo cambian de forma a medida que N aumenta de tamaño; p.ej. 1000 N + N^1.5 .

  

¿Hay otra forma además del análisis léxico o el análisis del código?

El análisis y el análisis léxico no son suficientes. También debe hacer algún razonamiento sobre el comportamiento del algoritmo. Y hacerlo de forma automática para un algoritmo previamente desconocido es difícil.

    
respondido por el Stephen C 07.09.2012 - 07:39
3

No pueden sin analizar el código.

Los ejemplos a continuación con "inflación / deflación artificial" de complejidad demuestran que simplemente medir el tiempo de ejecución del programa no es suficiente para estimar de forma confiable Big-O

void lets_trick_runtime(int n) {
   if (n == 10 || n == 25 || n == 118) {
      // unfair speed-up
      do_precalculated_solution_in_constant_time(n);
      return;
   }
   if (n == 11 || n == 26 || n == 119) {
      // unfair slow-down
      do_some_fake_processing_in_n_cube_time(n);
      return;
   }
   // fair solution
   do_general_solution_in_quadratic_time(n);
}

La estimación de tiempo de ejecución para lo anterior sería suceptible para dar estimaciones falsas: tiempo constante para los valores de n donde hay una solución calculada previamente y tiempo cúbico para los valores donde unfair slow-down patea en lugar de tiempo cuadrático "justo" .

    
respondido por el gnat 07.09.2012 - 10:46
1

Creo que esto no es posible.

Si ejecuta algunas pruebas con un número fijo de diferentes tamaños de entrada, puede calcular fácilmente un polinomio, que se aproximará a los tiempos de ejecución que ha medido muy bien. Así que terminas con un polinomio para cada programa posible, lo que significaría P = NP (¡sí!;)).

Si intentas hacerlo con manipulación simbólica, terminas en halting problem . Como no puede decidir si su programa se detendrá alguna vez, no puede decidir qué complejidad de tiempo de ejecución tendrá.

Sin embargo, puede haber casos muy especiales, donde el método posterior es posible. Pero estos casos tal vez sean tan pequeños, que es cuestionable si alguna vez se paga un esfuerzo.

    
respondido por el SpaceTrucker 02.10.2012 - 08:25
0

¿Cómo lo haría? La forma en que resuelvo casi cualquier problema no quiero sentarme y resolver . Yo simulo.

Para muchos problemas, puede ser suficiente ejecutar su algoritmo muchas veces utilizando una variedad de tamaños y luego ajustar una curva de regresión a esos resultados. Eso identificaría rápidamente algunos costos generales "fijos" de su algoritmo (la intersección de la curva) y la forma en que se incrementa a medida que aumenta el tamaño del problema.

Se necesitarán algunos retoques para capturar soluciones particularmente complicadas, pero especialmente si solo está buscando una estimación de bola de juego, debería poder obtenerla de esa manera, y ver cómo su estimación difiere de sus resultados reales y decide si es una aproximación aceptable.

La mayor debilidad en mi mente con este método es que si su algoritmo se escala realmente mal, ese paso inicial de "ejecutarlo un montón de veces" se pondrá feo. Pero, francamente, ese es el caso, solo debería ser un indicador de que es posible que desee retroceder y reconsiderar las cosas.

    
respondido por el Fomite 07.09.2012 - 09:29
0

Mi intuición es que una solución general a este problema es imposible; afirmando, como lo hace, a priori información sobre el tiempo de ejecución de los algoritmos sin ejecutarlos (alude al análisis léxico). Dicho esto, es posible que algún algoritmo heurístico para una clase (probablemente grande) de algoritmos (ya que lo hacemos todo el tiempo), pero un algoritmo general para hacer esto sería equivalente a resolver el Entscheidungsproblem que se sabe que no es posible (cf. Church, Turing, et al.). Estoy ~ 99.9% seguro de esto ahora que lo pienso ...

    
respondido por el veryfoolish 01.10.2012 - 19:24

Lea otras preguntas en las etiquetas