(не показано 12 промежуточных версий этого же участника)
Строка 1:
Строка 1:
−
<big>Цыганова Светлана, 974 гр.</big>
−
* Какие входные данные для алгоритма динамического программирования для упаковки
* Какие входные данные для алгоритма динамического программирования для упаковки
заставят его работать экспоненциально долго?
заставят его работать экспоненциально долго?
Строка 6:
Строка 4:
* А какие — за <m>O(n^3)</m>?
* А какие — за <m>O(n^3)</m>?
−
'''Решение'''
−
1) Экспоненциально долго алгоритм будет работать на частный случае подмножеств: каждое подмножество будет отвечать некоторому элементу, таким образом число подмножеств равно числу элементов, все подмножества попарно не пересекаются (диагональная матрица инцидентности). Тогда столбцов будет n. Для каждого столбца число объектов(совокупность решения, покрытия, размера покрытия) в листе X увеличивается в 2 раза (для каждого объекта на предыдущем шаге приписываем в лист ещё один объект). Таким образом для i-го столбца будет совершено <m>2^i</m> прохода по внутреннему циклу, и для последнего столбца - <m>2^n</m>. Таким образом после работы в X будет <m>2^n</m> объектов. Чтобы их записать в X, очевидно, надо было потратить экспоненциальное время. Таким образом на данном входе алгоритм работает экспоненциальное время. (Сейчас я считала, что подсчет newcov происходит за константное время. Вообще надо считать, что за линейное - тогда надо число операций умножить ещё на n)
+
<!--Вообще-то, решения уже есть-->
−
2) За кубическое время алгоритм будет работать, если матрица инцидентности будет нижней треугольной, а <m>m=n</m>. Тогда каждый внутренний цикл будет увеличивать число объектов в листе X на 1 - по сути будет дописываться в качестве решения следующий прочитанный столбец. Но для каждого столбца алгоритм будет проверять, что его покрытие не пересекается с покрытием текущего рассматриваемого решения - это будет за линейное время от числа элементов. Таким образом после рассмотрения i столбца в X будет (i+1) элемент. Тогда операций алгоритма будет
+
[[Категория:Решенные задачи]]
−
<latex>
+
−
$$(1+2+3+...+n)*n = \frac{1+n}{2}n*n = O(n^3)$$
+
−
</latex>
+
−
Первый множитель - сумма запусков внутреннего цикла для всех столбцов матрицы, второй - число операций в каждом внутреннем цикле. Искомый пример построен.
+
−
[[Category:На проверку]]
+
Версия 15:49, 20 мая 2020
Какие входные данные для алгоритма динамического программирования для упаковки