L'analyse de la complexité temporelle d'une fonction écrite en C

Question

J'exécutait problème Longest Common Subsequence en C. Je souhaite comparer le temps nécessaire pour l'exécution de la version récursive de la solution et la version de programmation dynamique. Comment puis-je trouver le temps nécessaire pour l'exécution de la fonction LCS dans les deux versions pour différentes entrées? Aussi je peux utiliser SciPy pour tracer ces valeurs sur un graphique et en déduire la complexité du temps?

Merci à l'avance,

Razor

Answer 1

Pour la deuxième partie de votre question: la réponse courte est oui, vous le pouvez. Vous devez obtenir les deux ensembles de données (une pour chaque solution) dans un format qui convient d'analyser avec de Python. Quelque chose comme:

x y z

sur chaque ligne, où x est la longueur de la séquence, y est le temps pris par la solution de dynamique, z est le temps pris par la solution récursive

Alors, 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 façon la plus simple à temps processeur de compte est d'utiliser la fonction de clock() time.h:

clock_t start, elapsed;

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

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

Puisque vous comparez simplement les différentes implémentations, vous n'avez pas besoin de convertir les horloges en unités en temps réel.

Answer 3

Il existe différentes façons de le faire. L'un des plus simple est de trouver un code qui fait haute résolution (microseconde ou moins) le calendrier des intervalles. Wrap appels aux fonctions de démarrage minuterie et minuterie d'arrêt autour de l'appel à la fonction LCS, puis imprimer le résultat temps écoulé:

#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)));

De même pour la fonction lcs_dynamic().

Si le temps d'une seule itération est trop petite, puis enrouler une boucle autour de la fonction. Je mets habituellement le code temporel en fonction, puis appeler que quelques fois pour obtenir des résultats cohérents.

Je peux vous indiquer le paquet illustré.

Oui, vous pouvez nourrir les résultats, avec soin, dans un emballage tel que SciPy graphiquement. De toute évidence, vous auriez à paramétrer la taille de test, et le temps le code plusieurs fois à chaque taille.