3622
правки
Изменения
м
→Время работы
Пускай все времена выполнения работ различны. Тогда все множества работ, используемые в качестве аргументов рекурсивного вызова функции можно представить в виде <tex>\langle i, j, k \rangle : \{ v \mid i \leqslant v \leqslant j \wedge p_v < p_k\}</tex>, <tex> i, j, k \in \{1, 2, \ldots, n\}</tex>.
У нас максимум <tex> p = \sum\limits_{i=1}^n p_i</tex> различных значений <tex>t</tex>. Значит, мы вызовем <tex> \mathrm{sequence}(t,I)}</tex> в худшем случае <tex>\mathcal{O}(n^3p)</tex> раз. Более того, для фиксированного <tex>k</tex> все значения <tex>\max\{p_v \mid v \in I_{ijk}\}</tex> для <tex>i, j = 1,\ldots, n,</tex> <tex>i < j</tex> могут быть сосчитаны за <tex>\mathcal{O}(n^2)</tex>.
Таким образом, мы получаем алгоритм, работающий за <tex>\mathcal{O}(n^3p)</tex> или <tex>\mathcal{O}(n^4p_{max})</tex>, где <tex>p_{max} = \max\limits_{i=1}^n p_i</tex>.
