Алгоритмы: Найти рекурсивное уравнение "разделяй и властвуй"
У меня есть следующий алгоритм "разделяй и властвуй" A1.
A1 делит задачу с размером n на 4 подзадачи с размером n / 4. Затем решите их и составьте решения за 12n раз.
Как я могу написать рекурсивное уравнение, которое дает время выполнения алгоритмов.
3 ответа
Отвечая на вопрос "Как мне написать рекурсивное уравнение, дающее время выполнения алгоритмов"
Вы должны написать это так: пусть T(n) обозначает время выполнения вашего алгоритма для входного размера n
T(n) = 4 * T (n / 4) + 12 * n;
Несмотря на то, что основная теорема дает кратчайший путь к ответу, необходимо понять происхождение времени выполнения Big O. Разделяй и властвуй повторяющиеся отношения записываются в виде T(n) = q * T(n/j) + cn, где q количество подзадач, j количество мы делим данные для каждой подзадачи, и cn это время, которое требуется для разделения / объединения / манипулирования каждой подзадачей на каждом уровне. cn также может быть cn^2 или же cкакой бы ни была среда выполнения.
В вашем случае у вас есть 4 подзадачи размера n/4, каждый уровень которых решается в 12n время, дающее рекуррентное соотношение T(n) = 4 * T(n/4) + 12n, Из этого повторения мы можем затем получить время выполнения алгоритма. Учитывая, что это отношение разделяй и властвуй, мы можем предположить, что базовый случай T(1) = 1,
Чтобы решить повторение, я буду использовать технику, названную заменой. Мы знаем это T(n) = 4 * T(n/4) + 12nпоэтому мы заменим T(n/4). T(n/4) = 4 * T(n/16) + 12(n/4), Включение этого в уравнение заставляет нас T(n) = 4 * (4 * T(n/16) + 12n/4) + 12n, который мы можем упростить до T(n) = 4^2 * T(n/16) + 2* 12n, Опять же, у нас еще есть много работы в уравнении, чтобы захватить работу на всех уровнях, поэтому мы заменяем T(n/16), T(n) = 4^3 * T(n/64) + 3* 12n, Мы видим появление паттерна и знаем, что хотим пройти весь путь до нашего базового случая, T(1)так, чтобы мы подставили, чтобы получить T(n) = 4^k*T(1) + k * 12n, Это уравнение определяет общий объем работы, который находится в алгоритме "разделяй и властвуй", потому что мы заменили все уровни в, однако у нас все еще есть неизвестная переменная k, и мы хотим ее с точки зрения n Мы получаем k решая уравнение n/4^k = 1 поскольку мы знаем, что достигли точки, в которой мы вызываем алгоритм только для одной переменной. Решаем и получаем что k = log4n, Это означает, что мы сделали log4n замены. Мы подключаем это для k и получить T(n) =4^log4n*T(1) + log4n * 12n, Мы упрощаем это до T(n) =n *1 + log4n * 12n, Так как это анализ Big O и log4n в O(log2n) из-за изменения базового свойства логарифмов, мы получаем, что T(n) = n + 12n * logn Который означает, что T(n) находится в Большой О nlogn,
Отношение повторения, которое лучше всего описывает, дается:
T(n)=4*T(n/4)+12*n
куда T(n)= время выполнения данного алгоритма для ввода размера n, 4= нет подзадач,n/4 = размер каждой подзадачи.
С использованием основной теоремы сложность времени рассчитывается так:theta(n*log n)