Изменения

Лемма: {{Теорема|statement=Время работы алгоритма MakeSchedule() — <tex> O(n^2) </tex> операций.|proof=Обозначим за <tex> P(n) </tex> время работы , необходимое для выполнения алгоритма MakeSchedule() на n работах. Очевидно, для корректно определенной функции P в силу структуры алгоритма должно выполняться неравенство: <tex> P(n) \ge сn + \sum\limits_{i = 1 }^{k} P(n_i) </tex> Здесь <tex> n_i </tex> - размер блока с номером <tex> i </tex>, построенного алгоритмом Blocks(). Заметим, что <tex> \sum\mid preclimits_{i = 1}^{k} n_i = n - 1</tex>. Если P(n) = an^2, pmtn, r_i то имеем: <tex> an^2 \ge cn + a \sum\mid f_limits_{maxi = 1} ^{k} n_i^2 </tex> —  Так как <tex> On^2 > (n- 1)^2 = (\sum\limits_{i = 1}^{k} n_i)^2 = \sum\limits_{i = 1}^{k} n_i^2+ 2\sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j </tex>, то можно переписать неравенство в следующем виде: <tex> 2a \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \ge cn </tex> Чтобы получить максимальную нижнюю оценку на <tex> a </tex>, оценим снизу <tex> \sum\limits_{i, j = 1}^{k} n_i n_j </tex>: Так как <tex> \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \ge \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} 1 \cdot n_j = \sum\limits_{j = 1}^{k} (k - 1) n_j = (k - 1) (n - 1) \ge \frac{nk}{4}</tex> Значит, при <tex> a \ge \frac{c}{2} \frac{n}{\frac{nk}{4}} = \frac{2c}{k} </tex> операцийтребуемое неравенство будет выполняться. }}