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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 17 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
<latex>
 
<latex>
 
Найдите такую функцию $T_A$, являющуюся временем работы некоторого алгоритма $A$,
 
Найдите такую функцию $T_A$, являющуюся временем работы некоторого алгоритма $A$,
и~входное вероятностное распределение $\mathrm{P}_n(x)$ (), что
+
и~входное вероятностное распределение $\mathrm{P}_n(x_n)$, что
 
$\mathrm{E}_n T_A = O(n^C)$, но $\mathrm{E}_n T^2_A \ne O(n^C)$.
 
$\mathrm{E}_n T_A = O(n^C)$, но $\mathrm{E}_n T^2_A \ne O(n^C)$.
 
</latex>
 
</latex>
  
 
;Вероятностное распределение: Вероятность появления каждой входной строки.
 
;Вероятностное распределение: Вероятность появления каждой входной строки.
 +
;<m>x_n</m>: вход длины n.
 +
  
[[Category:Нерешенные задачи]]
 
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->
 +
 +
[[Категория:Решенные задачи]]

Версия 15:49, 20 мая 2020

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