У меня есть алгоритм подсчета, для которого я пытаюсь получить общее описание big-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.
Вот построчное представление каждого времени выполнения
- Это простое разбиение, и я просто дам ему константу c1.
- max_k — небольшое число, всегда меньше n, возможно, около 4 или 5. Ниже я буду использовать k.
- Этот цикл всегда выполняется 2^k*(n выбирает k) раз
- Считая строку 1 константой, мы можем обобщить эту строку и знать, что в худшем случае она никогда не будет срабатывать более 2^n раз, но обычно будет выполняться часть 2^n раз, поэтому мы назовем ее (2^ п)/с2
- Это простая операция оператора if внутри всех этих циклов, поэтому c3.
Умножение всего этого вместе дает:
c1 * k * 2^k * (n choose k) * (2^n)/c2 * c3
Поскольку мне нужно представление большого O, игнорирование констант дает:
k * 2^k * (n choose k) * (2^n)
Известно, что (n выбирает k) ограничено сверху (n * e/k)^k, поэтому:
O(k * 2^k * (n * e / k)^k * (2^n))
Мой вопрос в том, что я могу здесь игнорировать... 2 ^ n, безусловно, является доминирующим термином, поскольку n всегда больше, чем k, и обычно намного больше. Можно ли упростить это до O (2 ^ n)? Или О(2^ужасно)? Или я должен оставить в 2 ^ k, как в O (2 ^ k * 2 ^ n)? (или оставить все термины?)
Насколько я понимаю, если k или max_k могут составить конкуренцию или превзойти n, то они жизненно необходимы. Но поскольку над ними всегда доминируют, можно ли их отбросить, как члены более низкого порядка полиномиального времени выполнения? Я полагаю, что весь экспоненциальный беспорядок времени работы сбивает меня с толку. Любые советы высоко ценится.
