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

<latex>
Найдите такую функцию $T_A$, являющуюся временем работы некоторого алгоритма $A$,
и~входное вероятностное распределение $\mathrm{P}_n(x_n)$, что
$\mathrm{E}_n T_A = O(n^C)$, но $\mathrm{E}_n T^2_A \ne O(n^C)$.
</latex>

;Вероятностное распределение: Вероятность появления каждой входной строки.
;<m>x_n</m>: вход длины n.


<!--Вообще-то, решения уже есть-->

[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]