Время O(nk)

По тем же соображениям, по которым мы пришли к времени выполнения O(n2), применяя алгоритм «грубой силы» ко всем парам множества из n элементов, можно получить время выполнения O(nk) для любой константы к при переборе всех под- множеств размера k.

Для примера возьмем задачу поиска независимого множества в графе, упоми- навшуюся в главе 1. Напомним, что множество узлов называется независимым, если никакие два узла не соединяются ребром. А теперь допустим, что для некоторой константы к мы хотим узнать, содержит ли входной граф G с n узлами независи- мое множество размера к. Естественный алгоритм «грубой силы» для этой задачи перебирает все подмножества из к узлов, и для каждого подмножества S проверяет существование ребра, соединяющего любые два узла из S. На псевдокоде это вы- глядит так:

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

Проверить, образует ли S независимое множество Если S является независимым множеством

Остановиться и объявить об успешном поиске Конец Если Конец цикла

Если не найдено ни одно независимое множество из к узлов Объявить о неудачном поиске Конец Если

Чтобы понять время выполнения этого алгоритма, необходимо учесть два фактора. Во-первых, общее количество к-элементных подмножеств в множестве из n элементов равно

Так как к считается постоянной величиной, эта величина имеет порядок O(nк). Следовательно, внешний цикл алгоритма, перебирающий все к-элементные под- множества n узлов графа, выполняется за O(nк) итераций.

Внутри цикла необходимо проверить, образует ли заданное множество S из к узлов независимое множество. Согласно определению независимого множества, необходимо для каждой пары узлов проверить, соединяются ли они ребром. Это типичная задача поиска по парам, которая, как было показано ранее при обсужде-


нии квадратичного времени выполнения, требует проверки , то есть О(к2) пар при постоянных затратах времени на каждую пару.

Итак, общее время выполнения равно O(к2nк). Так как к считается константой, а константы в записи O() могут опускаться, это время выполнения можно записать в виде O(nk).

Поиск независимых множеств — типичный пример задачи, которая считается вычислительно сложной. В частности, считается, что никакой алгоритм поиска независимого множества из к узлов в произвольных графах не может избежать за- висимости от к в показателе степени. Но, как будет показано в главе 10 в контексте похожей задачи, даже если согласиться с тем, что поиск методом «грубой силы» по к-элементным подмножествам неизбежен, существуют разные варианты реа- лизации, приводящие к существенным различиям в эффективности вычислений.

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

Еще по теме Время O(nk):

  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. Прошлое время.
  18. Поясное время.
  19. Декретное время