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

Обновить

November 2018

Просмотры

4.9k раз

8

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

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

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

2 ответы

16

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

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

при к <= NK:

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})

3

Как следовать до @amit, верхняя граница-мин {к, пк} равно п / 2.

Таким образом, верхняя граница для "п выбрать к" сложность O (N ^ (п / 2))

Связанные вопросы