Изменения

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

J2pij1Lmax

9 байт добавлено, 01:31, 7 июня 2016
м
Асимптотика
==Асимптотика==
Суммарное количество операций равно <tex>r</tex>. Первый шаг алгоритма занимает <tex>O(r)</tex>, так как каждая операция добавляется либо в <tex>L</tex>, либо в <tex>Z</tex>. На втором шаге каждая операция назначается единожды, то есть на втором шаге также выполняется <tex>O(r)</tex> действий. И, наконец, суммарное время всех вызовов функции <tex>\mathrm{schedule}</tex> также равно <tex>O(r)</tex>, так как суммарное количество итераций циклов внутри этой функции не превышает <tex>O(r)</tex>. Итого, время работы алгоритма <tex>O(r)</tex>.
==Доказательство==

Навигация