Для алгоритма с T (n) = a2 ^ (kn) решите, сколько времени потребуется, чтобы решить задачу с n = 20

Question

У меня проблемы с подсчетом времени, затрачиваемого на решение такой задачи:

Временная сложность алгоритма определяется путем измерения. При размере задачи n = 12 мы измерили время выполнения алгоритма 0,484 с, а при n = 14 - 9,844 с. Будем считать, что временная сложность алгоритма T (n) = a2 ^ (kn)

. Подсчитайте, сколько времени потребуется алгоритму для решения задачи размера n = 20!

Answer 1

Если вам просто нужен математический анализ вместо оценки,

T(12) = a. (2 ^ (12.k)) . 12.k (eq1)

T(14) = a. (2 ^ (14.k)) . 14.k (e12)

Разделите eq1 на eq2, a отменяется, все, что у вас есть, это k и константы. Решите для k.

Теперь поместите значение k в eq1 или eq2, чтобы получить значение a.

Наконец, у вас есть окончательная форма функции , просто подключите n = 20.

Answer 2

Подобные упражнения демонстрируют непонимание того, что такое временная сложность.

Временная сложность алгоритма определяется путем измерения.

Это невозможно сделать надежно. Измерение не является надежным способом определения временной сложности любого алгоритма. Он может просто служить подтверждением предоставленного доказательства, основанного на анализе алгоритма .

Подсчитайте, сколько времени потребуется алгоритму для решения задачи размера n = 20!

Невозможно. Знание временной сложности алгоритма и нескольких измерений может помочь лишь приблизительно оценить, каким может быть на этот раз , но никаких гарантий нет. Это вполне может быть 10000 или 90000 без нарушения заданной временной сложности.