Полиномиальный в среднем алгоритм для задачи упаковки/Задачи/ex-packing-average-bad-and-good-data — различия между версиями
Tsyganova (обсуждение | вклад) |
Tsyganova (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
'''Решение''' | '''Решение''' | ||
| − | 1) Экспоненциально долго алгоритм будет работать на частный случае подмножеств: каждое подмножество будет отвечать некоторому элементу, таким образом число подмножеств равно числу элементов, все подмножества попарно не пересекаются (диагональная матрица инцидентности). Тогда столбцов будет n. Для каждого столбца число объектов(совокупность решения, покрытия, размера покрытия) в листе X увеличивается в 2 раза (для каждого объекта на предыдущем шаге приписываем в лист ещё один объект). Таким образом для i-го столбца будет совершено <m>2^i</m> прохода по внутреннему циклу, и для последнего столбца - <m>2^n</m>. Таким образом после работы в X будет <m>2^n</m> объектов. Чтобы их записать в X, очевидно, надо было потратить экспоненциальное время. Таким образом на данном входе алгоритм работает экспоненциальное время. | + | 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:На проверку]] | [[Category:На проверку]] | ||
Версия 19:10, 1 декабря 2014
Цыганова Светлана, 974 гр.
- Какие входные данные для алгоритма динамического программирования для упаковки
заставят его работать экспоненциально долго?
- А какие — за ?
Решение
1) Экспоненциально долго алгоритм будет работать на частный случае подмножеств: каждое подмножество будет отвечать некоторому элементу, таким образом число подмножеств равно числу элементов, все подмножества попарно не пересекаются (диагональная матрица инцидентности). Тогда столбцов будет n. Для каждого столбца число объектов(совокупность решения, покрытия, размера покрытия) в листе X увеличивается в 2 раза (для каждого объекта на предыдущем шаге приписываем в лист ещё один объект). Таким образом для i-го столбца будет совершено прохода по внутреннему циклу, и для последнего столбца - . Таким образом после работы в X будет объектов. Чтобы их записать в X, очевидно, надо было потратить экспоненциальное время. Таким образом на данном входе алгоритм работает экспоненциальное время. (Сейчас я считала, что подсчет newcov происходит за константное время. Вообще надо считать, что за линейное - тогда надо число операций умножить ещё на n)
2) За кубическое время алгоритм будет работать, если матрица инцидентности будет нижней треугольной, а . Тогда каждый внутренний цикл будет увеличивать число объектов в листе X на 1 - по сути будет дописываться в качестве решения следующий прочитанный столбец. Но для каждого столбца алгоритм будет проверять, что его покрытие не пересекается с покрытием текущего рассматриваемого решения - это будет за линейное время от числа элементов. Таким образом после рассмотрения i столбца в X будет (i+1) элемент. Тогда операций алгоритма будет Первый множитель - сумма запусков внутреннего цикла для всех столбцов матрицы, второй - число операций в каждом внутреннем цикле. Искомый пример построен.