Изменения

Перейти к: навигация, поиск

PpmtnriLmax

835 байт добавлено, 00:19, 10 июня 2012
Нет описания правки
Исходя из этого, расписание строится выполнением работы <tex>J_{iK}</tex> с временем выполнения <tex>x_{iK}</tex> в интервале <tex>I_K</tex>.
 
Т.к. сеть содержит <tex>O(N)</tex> элементов, значит максимальный поток в ней можно найти за <tex>O(n^3)</tex>. Кроме того, построение "окон" выполнения работ займет <tex>O(N^2)</tex>. Т.о. указанный выше алгоритм потребует <tex>O(N^3)</tex> операций.
 
Для решения данной задачи мы используем бинпоиск по <tex>L</tex> значениям, а значит, получаем алгоритм с <tex>\varepsilon</tex>-приближенной сложностью <tex>O (n^3(log(n) + log(1 / \varepsilon) + log(\max\limits_{j=1}^{n} p_j)) </tex>, потому как <tex>L_{max}</tex>, ограничен <tex>n \max\limits_{j=1}^{n}p_j</tex>
419
правок

Навигация