Кубическое время

Более сложные группы вложенных циклов часто приводят к появлению алгорит- мов, выполняемых за время O(n3). Для примера рассмотрим следующую задачу. Имеются множества S1, S2, ..., Sn, каждое из которых является подмножеством {1, 2, ..., n}; требуется узнать, можно ли найти среди этих множеств непересекаю- щуюся пару (то есть два множества, не имеющих общих элементов).

Какое время потребуется для решения этой задачи? Предположим, каждое множество Si представлено таким образом, что элементы Si могут быть обработаны с постоянными затратами времени на элемент, а проверка того, входит ли задан- ное число p в S , также выполняется за постоянное время. Ниже описано наиболее прямолинейное решение задачи.

Для всех пар множеств S и S'

Определить, имеют ли S и Sj общий элемент Конец цикла

Алгоритм выглядит конкретно, но чтобы оценить его время выполнения, по- лезно преобразовать его (по крайней мере концептуально) в три вложенных цикла.

Для каждого множества S

Для каждого из оставшихся множеств S.

Для каждого элемента p множества St

Определить, принадлежит ли p множеству S.

Конец цикла

Если ни один элемент S не принадлежит S.

Сообщить, что множества St и S. являются непересекающимися Конец Если Конец цикла Конец цикла

80 Глава 2. Основы анализа алгоритмов

Каждое из множеств имеет максимальный размер n, поэтому внутренний цикл выполняется за время O(n). Перебор множеств Sj требует O(n) итераций внутрен- него цикла, а перебор множеств S. требует O(n) итераций внешнего цикла. Пере- множая эти три множителя, мы получаем время выполнения O(n3).

Для этой задачи существуют алгоритмы, улучшающие время выполнения O(n3), но они достаточно сложны. Более того, не очевидно, дают ли эти улучшенные алго- ритмы практический выигрыш при входных данных разумного размера.

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

Еще по теме Кубическое время:

  1. Время сейчас такое – время мудрости пришло!
  2. 14. 4. Рабочее время и время отдыха
  3. Зарубка на носу Дай время себе, дай время ребенку
  4. Время
  5. Время
  6. Время
  7. Время
  8. Всемирное время.
  9. Местное время.
  10. 1.2.2. Время отдыха
  11. 1.2.1 Рабочее время
  12. ВРЕМЯ
  13. ВРЕМЯ РЕАКЦИИ
  14. «Время»
  15. Настоящее время.
  16. Летнее время
  17. Прошлое время.