689
правок
Изменения
м
→Время работы
{{Теорема
|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>
