Время O nk

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

Для примера возьмем задачу поиска независимого множества в графе. Напомним, что множество узлов называется независимым, если никакие два узла не соединяются ребром. А теперь допустим, что для некоторой константы k мы хотим узнать, содержит ли входной граф G с n узлами независимое множество размера 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 в показателе степени. Но даже если согласиться с тем, что поиск методом «грубой силы» по k-элементным подмножествам неизбежен, существуют разные варианты реализации, приводящие к существенным различиям в эффективности вычислений.