Анализ временной сложности функции, написанной на языке C

Question

Я выполнял самую большую проблему с общим подпоследовательством в C. Я хочу сравнить время, затраченное на выполнение рекурсивной версии решения и версии динамического программирования. Как найти время, затрачиваемое на выполнение функции LCS в обеих версиях для различных входов? Также я могу использовать SciPy для построения этих значений на графике и определения временной сложности?

Спасибо заранее,

Бритва

Answer 1

Для второй части вашего вопроса: короткий ответ - да, вы можете. Вам нужно получить два набора данных (по одному для каждого решения) в формате, который удобно анализировать с помощью Python. Нечто подобное:

хугу

на каждую строку, где х длина последовательности, у этого время, необходимое динамическое растворем, г этого время, затраченное на рекурсивном раствор

Затем в 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

Самый простой способ для учета времени процессора является использование функции clock() из time.h:

clock_t start, elapsed; 

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

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

Поскольку вы просто сравнение различных реализаций, вы дон Не нужно преобразовывать часы в единицы реального времени.

Answer 3

Существуют различные способы сделать это. Один из простых заключается в том, чтобы найти некоторый код, который выполняет временные интервалы с высоким разрешением (микросекунда или меньше). Заверните вызовы к стартовому таймера и остановки таймера функции вокруг вызова функции ЛВП, а затем распечатать получившийся истекшее время:

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

Аналогично для функции lcs_dynamic().

Если время для одной итерации слишком мал, то оберните петлю вокруг функции. Обычно я устанавливаю код синхронизации в функцию, а затем вызываю это несколько раз, чтобы получить согласованные результаты.

Я могу указать на представленный пакет.

Да, вы можете с уверенностью накормить результаты в виде графического пакета, такого как SciPy. Очевидно, вам придется параметризовать размер теста и время кода несколько раз при каждом размере.