|
|
| Строка 1: |
Строка 1: |
| − | == Цыганова Светлана, 974гр. ==
| |
| | Придумайте входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время. | | Придумайте входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время. |
| | | | |
| − | <big>Решение:</big>
| + | [[Category:Решенные задачи]] |
| − | | + | <!--Вообще-то, решения уже есть--> |
| − | <latex> | + | |
| − | Рассмотрим следующий список предметов (над чертой - стоимость, под чертой - вес предмета, обозначения, как в книге):
| + | |
| − | | + | |
| − | $\frac{1}{2^0}; \frac{1}{2^1};\frac{1}{2^2};\frac{1}{2^3};\frac{1}{2^4};...\frac{1}{2^n}$
| + | |
| − | | + | |
| − | И пусть вместимость рюкзака будет равна B = 2n
| + | |
| − | | + | |
| − | Легко убедиться, что на каждой итерации алгоритма список частичных сумм будет увеличиваться в 2 раза, следовательно в конце работы алгоритма рассмотренных наборов будет $2^{n+1}$. Из этого следует как минимум экспоненциальное время добавление новой частичной суммы, и экспоненциальное время поиска наиболее дорогой частичной суммы. Пример приведен.
| + | |
| − | | + | |
| − | Пример на реальных числах, чтобы показать, как число частичных сумм увеличивается вдвое. Возьмем n = 3. Тогда список: $\frac{1}{1}; \frac{1}{2};\frac{1}{4};\frac{1}{8}$, B = 16
| + | |
| − | | + | |
| − | Поитерационный список частичных сумм:
| + | |
| − | | + | |
| − | 0) $\frac{0}{0}$
| + | |
| − | | + | |
| − | 1) $\frac{0}{0}; \frac{1}{1}$
| + | |
| − | | + | |
| − | 2) $\frac{0}{0}; \frac{1}{1}; \frac{1}{2}; \frac{2}{3}$
| + | |
| − | | + | |
| − | 3) $\frac{0}{0}; \frac{1}{1}; \frac{1}{2}; \frac{2}{3}; \frac{1}{4}; \frac{2}{5}; \frac{2}{6}; \frac{3}{7}$
| + | |
| − | | + | |
| − | 4) $\frac{0}{0}; \frac{1}{1}; \frac{1}{2}; \frac{2}{3}; \frac{1}{4}; \frac{2}{5}; \frac{2}{6}; \frac{3}{7}; \frac{1}{8}; \frac{2}{9}; \frac{2}{10}; \frac{3}{11}; \frac{2}{12}; \frac{3}{13}; \frac{3}{14}; \frac{4}{15}$
| + | |
| − | | + | |
| − | Итого наборов $2^4$.
| + | |
| − | | + | |
| − | </latex>
| + | |
| − | [[Category:На проверку]]
| + | |
Версия 21:32, 24 декабря 2014
Придумайте входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время.