Анализ алгоритма

Осталось проанализировать время выполнения Segmented-Least-Squares. Сначала необходимо вычислить значения всех погрешностей наименьших квадратов e... Чтобы учесть время выполнения, расходуемое на эти вычисления, заметим, что существуют O(n2) пар (i, j), для которых эти вычисления необходимы; для каждой пары (i, j) можно использовать формулу, приведенную в начале этого раздела, для вычисления e за время O(n).
Следовательно, общее время выполнения для вы- числения всех значений e.. равно O(n3).

Алгоритм состоит из n итераций для значений j = 1, ..., n. Для каждого значения j необходимо определить минимум в рекуррентном отношении (6.7) для заполнения элемента массиваMj]; это занимает время O(n) для каждого j, что в сумме дает O(n2). Итак, после определения всех значений e.. время выполнения равно O(n2)[7].

6.4.

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

Еще по теме Анализ алгоритма:

  1. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  4. АЛГОРИТМ
  5. АЛГОРИТМ УДАЧИ
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. 2. Специфика и алгоритмы работы с источниками.
  9. Алгоритм обработки результатов.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. Принципы анализа происшествия.
  13. АНАЛИЗ