Полиномиальный в среднем алгоритм для задачи о рюкзаке/Задачи/Проблемы определения «в среднем» — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 8: Строка 8:
 
;<m>x_n</m>: вход длины n.
 
;<m>x_n</m>: вход длины n.
  
[[Category:На проверку]]
+
[[Category:Решенные задачи]]
 
+
<!--Вообще-то, решения уже есть-->
<latex>
+
Допустим входные данные распределены равномерно. Тогда мат. ожидание времени работы алгоритма:
+
$\mathrm{E}_n T_A = \frac{T_A(x_1) + ... + T_A(X_{2^n})}{2^n}$, а $\mathrm{E}_n T^2_A = \frac{T^2_A(x_1) + ... + T^2_A(X_{2^n})}{2^n}$.
+
Рассмотрим вариант, когда алгоритм будет работать за время n на всех входах кроме одного, а на одном входе будет работать за время $2^n$. Тогда
+
$\mathrm{E}_n T_A = \frac{2^n + (2^n - 1)*n}{2^n} ≈ O(n)$, а
+
$\mathrm{E}_n T^2_A = \frac{2^n^2 + (2^n - 1)*n^2}{2^n} ≈ O(2^n + n^2)$
+
</latex>
+

Версия 02:42, 26 декабря 2014

Вероятностное распределение
Вероятность появления каждой входной строки.
вход длины n.