Вопросы для интервью, в которых я начинаю с "это может быть решена путем создания всех возможных комбинаций для элементов массива", обычно означают, что я могу найти что-то лучшее.
В любом случае я хотел бы добавить: "Я определенно предпочел бы другое решение, так как это O (X)". Вопрос: что такое сложность O (X) для создания всех комбинаций для заданного множества?
Я знаю, что есть n!/(n-k)! k! комбинаций (биномиальных коэффициентов), но как получить из них обозначение Big-O?
Во-первых, нет ничего плохого в использовании 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})
В качестве продолжения @amit верхняя граница min {k, n-k} равна n/2.
Следовательно, верхняя граница для сложности "n выбирает k" равна O (n ^ (n/2))
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})
Я знаю, что это старый вопрос, но он пользуется популярностью в 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, но не знаю, есть ли более жесткая верхняя граница, которая лучше ее описывает.