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

Более сложные группы вложенных циклов часто приводят к появлению алгоритмов, выполняемых за время O(n3). Для примера рассмотрим следующую задачу. Имеются множества S1, S2, …, Sn, каждое из которых является подмножеством

{1, 2, …, n}; требуется узнать, можно ли найти среди этих множеств непересекающуюся пару (то есть два множества, не имеющих общих элементов).

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

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

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

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

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

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

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

Конец цикла

Если ни один элемент Si не принадлежит Sj

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

Конец цикла Конец цикла.

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

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