Полиномиальный в среднем алгоритм для задачи о рюкзаке/Задачи/Проблемы определения «в среднем» — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
Larisa (обсуждение | вклад) |
||
| Строка 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> | ||
Версия 14:18, 12 декабря 2014
- Вероятностное распределение
- Вероятность появления каждой входной строки.
- вход длины n.