El análisis de la complejidad de tiempo de una función escrita en C

Question

Me estaba poniendo en práctica un problema común más larga subsecuencia en C. deseo de comparar el tiempo necesario para la ejecución de la versión recursiva de la solución y la versión de la programación dinámica. ¿Cómo puedo encontrar el tiempo necesario para ejecutar la función de LCS en ambas versiones para diferentes entradas? También puedo usar SciPy para trazar estos valores en un gráfico y deducir la complejidad del tiempo?

Gracias de antemano,

Razor

Answer 1

Para la segunda parte de su pregunta: la respuesta corta es sí, se puede. Que necesita para obtener los dos conjuntos de datos (una para cada solución) en un formato que es conveniente analizar con desde Python. Algo así como:

x y z

en cada línea, donde x es la longitud de la secuencia, y es el tiempo empleado por la solución dinámica, z es el tiempo empleado por la solución recursiva

A continuación, en Python:

# Load these from your data sets.
sequence_lengths = ...
recursive_times  = ...
dynamic_times    = ...

import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
p1 = ax.plot(sequence_lengths, recursive_times, 'r', linewidth=2)
p2 = ax.plot(sequence_lengths, dynamic_times,   'b', linewidth=2)

plt.xlabel('Sequence length')
plt.ylabel('Time')
plt.title('LCS timing')
plt.grid(True)
plt.show()

Answer 2

La forma más sencilla de tiempo de procesador cuenta es el uso de la función clock() de time.h:

clock_t start, elapsed;

start = clock();
run_test();
elapsed = clock() - start;

printf("Elapsed clock cycles: %ld\n", (long)elapsed);

Dado que usted es simplemente comparando las distintas aplicaciones, no es necesario convertir los relojes en unidades de tiempo real.

Answer 3

Hay varias maneras de hacerlo. Uno de los más simple es encontrar un código que hace la sincronización de los intervalos de alta resolución (más pequeño o microsegundos). Envoltura de llama a las funciones de arranque y parada del temporizador temporizador alrededor de la llamada a la función de LCS, a continuación, imprimir el tiempo transcurrido resultante:

#include "timer.h"

Clock clk;
char elapsed[32];

clk_start(&clk);
lcs_recursive();
clk_stop(&clk);
printf("Elapsed time (recursive): %s\n",
       clk_elapsed_us(&clk, elapsed, sizeof(elapsed)));

Del mismo modo para la función lcs_dynamic().

Si el tiempo para una sola iteración es demasiado pequeño, entonces envolver un lazo alrededor de la función. Yo suelo poner el código de tiempo en una función, y luego llamo a eso un par de veces para obtener resultados consistentes.

Me puede señalarle al envase ilustrado.

Sí, se puede alimentar a los resultados, con cuidado, en un paquete de graficar como SciPy. Está claro que habría que parametrizar el tamaño de la prueba, y la hora del código varias veces en cada tamaño.