Реализация и время выполнения

Алгоритм может выполняться за время O(n log n). Сначала n заявок следует от- сортировать в порядке конечного времени и пометить их в этом порядке; соот- ветственно предполагается, что f(i) < f(j), когда i < j.
Этот шаг выполняется за время O(n log n). За дополнительное время O(n) строится массив «S[1... n], в котором элемент S[i] содержит значение s(i).

Теперь выбор заявок осуществляется обработкой интервалов в порядке воз- растания f (i). Сначала всегда выбирается первый интервал; затем интервалы перебираются по порядку до тех пор, пока не будет достигнут первый интервал j, для которого s( j) > f(1); он также включается в результат. В более общей форму- лировке, если последний выбранный интервал заканчивается во время f перебор последующих интервалов продолжается до достижения первого интервала j, для которого s(j) > f Таким образом, описанный выше жадный алгоритм реализуется за один проход по интервалам с постоянными затратами времени на интервал. Следовательно, эта часть алгоритма выполняется за время O(n).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Реализация и время выполнения:

  1. Вторая зрелость – время реализации своей мечты
  2. Статья 849. Права заказчика во время выполнения работы
  3. Статья 1196. Возмещение вреда, причиненного физическому лицу во время выполнения им договорных обязательств
  4. Время сейчас такое – время мудрости пришло!
  5. 14. 4. Рабочее время и время отдыха
  6. Зарубка на носу Дай время себе, дай время ребенку
  7. 3.3. Дальнейшая реализация проекта
  8. Глава 6. Реализация права
  9. 4.2. Реализация
  10. 4. Реализация прав по ипотеке
  11. 10. Реализация заложенного имущества