Упрощение сложностей Big-O этого экспоненциального алгоритма

Question

У меня есть алгоритм подсчета, для которого я пытаюсь получить общее описание большого o. Он ужасно вложен и ужасно экспоненциальен. Вот оно:

1. For each T_i in T 
2. For k = 1 to max_k 
3. For each of 2^k*(n choose k) items 
4. For each t in T_i 
5. check if the item is in t...etc. 

Вот идея линия за линией каждого времени выполнения

1. Это простое разделение и я собираюсь просто дать ему постоянную c1.
2. max_k - небольшое число, всегда меньше n, возможно, около 4 или 5. Я буду использовать k ниже.
3. Эта петля всегда работает 2^k * (n выбирает k) раз
4. Рассматривая константу 1, мы можем обобщить эту строку и знать, что она не будет срабатывать больше, чем 2^n раз в общем случае в худшем случае, но обычно будет работать от 2^n раз, поэтому мы будем называть это (2^n)/c2
5. Это простая операция if-statement внутри всех этих циклов, поэтому c3.

Умножив все это дает:

c1 * k * 2^k * (n choose k) * (2^n)/c2 * c3 

Поскольку я хочу представление большой-O, игнорируя константы дает:

k * 2^k * (n choose k) * (2^n) 

Известно, что (п выбирают к) ограничен выше: (n * e/k)^k, поэтому:

O(k * 2^k * (n * e/k)^k * (2^n)) 

Мой вопрос в том, wh я могу игнорировать здесь ... 2^n, безусловно, является доминирующим термином, так как n всегда больше k и, как правило, гораздо более. Можно ли это упростить до O (2^n)? Или O (2^ужасно)? Или оставить в 2^k, как и в O (2^k * 2^n)? (или оставить все условия в?)

Я понимаю, что если k или max_k могут конкурировать или превосходить n, то они жизненно важны. Но так как они всегда доминируют, их можно отбросить как члены младшего порядка полиномиального времени работы? Я предполагаю, что все экспоненциальные беспорядки времени путают меня. Любые советы высоко ценится.

Answer 1

Я понимаю, что если к или max_k могут конкурировать или превосходить п, то они являются жизненно важными

Правда, но наоборот нет - значит - это не может быть проигнорировано, когда его приходит к большой нотации O, даже если она не конкурирует с n. Его можно игнорировать, только если max_k ограничено константой (существует постоянная c такая, что k <= c). Например, алгоритмы O(n * logk) не являются O(n), так как фактор k не ограничен и, следовательно, существует k такой, что nlogk > c*n для каждой константы c.

Поскольку вы получили продукт, все, что вы можете игнорировать, это константы, которые в вашем случае - это только e, получая вас O(k*2^k * (n/k)^k * 2^n).

Если kявляется ограниченным, то вы можете удалить его из выражения, а также в больших обозначениях O, и вы получите O(n^k* 2^n).Обратите внимание, что даже в этом случае, хотя и в n^k << 2^n, он по-прежнему не может быть проигнорирован, потому что для каждой константы c существует n такой, что c*2^n < n^k *2^n, поэтому алгоритм не является O(2^n).

Меньшие факторы можно игнорировать, когда дело доходит до добавления. Если k < n, то O(n + k) = O(n), потому что есть константы c,N такие, что для всех n > N: c*n < n + k, но это, конечно, не относится к делу.