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

Question

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

Заранее спасибо,

Бритва

Answer 1

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

xyz

На каждой строке, где x - длина последовательности, y - это время, затрачиваемое динамическим решением, z - это время, затрачиваемое рекурсивным решением

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

Есть различные способы сделать это. Одним из самых простых является найти какой -то код, который выполняет время с высоким разрешением (микросекунд или меньше) интервалов. Оберните вызовы в функции начала TIMER и Stop-Timer вокруг вызова к функции LCS, затем распечатайте полученное время:

#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. Очевидно, что вам придется параметризовать размер теста, и время кода несколько раз в каждом размере.