Время O nk

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

Естественный алгоритм «грубой силы» для этой задачи перебирает все подмножества из k узлов, и для каждого подмножества S проверяет существование ребра, соединяющего любые два узла из S. На псевдокоде это вы- глядит так:

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

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

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

Конец цикла

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

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

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

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

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