сложность комбинаторной функции

Question

Как классифицируется сложность алгоритма, связанного с комбинаторными операциями.

Допустим, вводом является m, n, а сложность определяется C (m, n). (C - комбинационная функция выбора m из n). Вопрос в том, как сложность следует классифицировать, а не просто давать C (m, n).

Я имею в виду, чтобы дать представление о времени выполнения алгоритма, можно сказать, что алгоритм имеет полиномиальную экспоненциальную сложность по времени. Но что делать с C (m, n)?

Я знаю, что факториалы можно аппроксимировать, используя приближение Стирлинга , но результат все еще слишком сложен, чтобы поместить его в класс сложности.

Answer 1

Вы не можете "поместить его в класс сложности", потому что это не время выполнения с одной переменной.

Это «асимптотическое поведение» не определено, потому что какую переменную мы должны рассматривать, чтобы приблизиться к бесконечной? Даже если мы сказали, что оба подхода бесконечны lim {n->inf, m->inf} nCm не определено, потому что их относительные значения не определены. То есть поведение зависит не только от того, что n и m больше определенного значения, но и от их относительных значений.

Сложность зависит от двух переменных, и nCm является совершенно допустимой функцией сложности.

Если у вас есть разумное приближение для m относительно n, то вы можете классифицировать его более легко. Может быть, стоит отработать случаи, когда m = O(n), m = O(1).
Или, где m = [kn] и 0 <= k <= 1 - это константа + формула Стилринга, вы получаете хорошее соотношение в одной переменной, но при этом можете учитывать значения m относительно k.

Answer 2

Если вы настаиваете на сохранении как m, так и n, то это будет трудно сделать лучше, чем в приближении Стирлинга.Верхняя граница только для m равна C (m, m / 2), которая асимптотически равна 2 ^m / √m и, следовательно, экспоненциальна.