Сложность при создании всех комбинаций

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

В любом случае я хотел бы добавить: "Я определенно предпочел бы другое решение, так как это O (X)". Вопрос: что такое сложность O (X) для создания всех комбинаций для заданного множества?

Я знаю, что есть n!/(n-k)! k! комбинаций (биномиальных коэффициентов), но как получить из них обозначение Big-O?

Ответы

Ответ 1

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

Если вы хотите посмотреть на размер подмножества k как константу,

для k <= n-k:

n! / ((n-k)!k!) = ((n-k+1) (n-k+2) (n-k+3) ... n ) / k!

Но выше на самом деле (n^k + O(n^(k-1))) / k!, который находится в O(n^k)

Аналогично, если n-k<k, вы получаете O(n^(n-k))

Что дает нам O(n^min{k,n-k})

Ответ 2

В качестве продолжения @amit верхняя граница min {k, n-k} равна n/2.

Следовательно, верхняя граница для сложности "n выбирает k" равна O (n ^ (n/2))

Ответ 3

case1: если nk <k

Предположим, что n = 11, k = 8 и nk = 3, тогда

 n!/(n-k)!k! = 11!/(3!8!)= 11x10x9/3!
 let suppose it is (11x11x11)/6 = O(11^3) and 11 was equal to n so O(n^3) and also n-k=3 so it become O(n^(n-k))

case2: если k <nk

Предположим, что n = 11, k = 3 и nk = 8, тогда

 n!/(n-k)!k! = 11!/(8!3!)= 11x10x9/3!
 let suppose it is (11x11x11)/6 = O(11^3) and 11 was equal to n so O(n^3) and also k=3 so it become O(n^(k))

Что дает нам O (n ^ min {k, nk})

Ответ 4

Я знаю, что это старый вопрос, но он пользуется популярностью в Google, и IMHO имеет неправильно отмеченный принятый ответ.

C(n,k) = n Choose k = n! / ( (n-k)! * k!)

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

∑ C(n,k) ∀ k ∊ (1..n).

так как это выражение представляет power-set. На английском языке вышеприведенное выражение представляет: add C(n,k) for all k from 1 to n. Мы знаем, что это имеет элементы 2 ^ n.

Таким образом, C(n, k) имеет верхнюю границу 2 ^ n, которая определенно меньше, чем n ^ k для любого n, k > 3, and k < n.

Поэтому, чтобы ответить на ваш вопрос, C(n, k) наверняка имеет верхнюю границу 2 ^ n, но не знаю, есть ли более жесткая верхняя граница, которая лучше ее описывает.