Изменения

Если для получения работы <tex> j </tex> с минимальным значением <tex> q(j) </tex> использовать очередь с приоритетами, а для поиска родителям вершины использовать систему непересекающихся множеств, то время работы алгоритма будет <tex> O(n\log{n}) </tex>.  == Доказательство оптимальности алгоритма =={{Теорема|id = theorem2|statement = Алгоритм <tex> 1 \mid outtree \mid \sum w_i C_i</tex> строит оптимальное расписание.|proof = Доказательство проведём по индукции. Очевидно, что для одной вершины алгоритм построит оптимальное расписание. Пусть теперь он может составить оптимальную последовательность назначенных работ числом меньше <tex> n </tex>. Пусть также работы <tex> i, j </tex> {{---}} работы, которые объединяться на первом шаге алгоритма. Тогда оптимальное расписание <tex> R </tex> можно представить следующим образом: <tex> \pi \colon \pi (1), ..., \pi (k), i, j, \pi (k + 3), ..., \pi (n) </tex> После объединения работ <tex> i </tex> и <tex> j </tex> в одну расписание <tex> R' </tex> примет такой вид: <tex> \pi ' \colon \pi (1), ..., \pi (k), I, \pi (k + 3), ..., \pi (n) </tex> где <tex> I = \{i, j\}, ~w(I) = w(i) + w(j), p(I) = p(i) + p(j)</tex>. Обозначим за <tex> f_n(\pi ), ~f_{n-1}(\pi ') </tex> целевые функции для последовательностей <tex> \pi </tex> и <tex> \pi ' </tex> соответственно. Тогда <tex>f_n(\pi ) - f_{n-1}(\pi ') \\ = w(i)p(i) + w(j)(p(i) + p(j)) - (w(i) + w(j))(p(i) + p(j)) = -w(i)p(j) ~(*)</tex> Следовательно, расписание <tex> R </tex> будет оптимальным тогда и только тогда, когда расписание <tex> R' </tex> будет оптимальным. А по предположению индукции наш алгоритм составит оптимальное расписание для последовательности <tex> \pi ' </tex>. Теперь разделим обе части равенства <tex> (*) </tex> на <tex> w(i)w(j) </tex>. Получим, что расстояние между целевыми функциями равно <tex dpi = 150> -\frac{p(j)}{w(j)} = -\frac{1}{q(j)} </tex> Это расстояние минимально (по модулю), так как мы выбирали работу <tex> j </tex> с максимальным значением <tex> q(j) </tex>. Из этих утверждений и следует оптимальность построенного алгоритмом расписания. }}