Анализ временной сложности с использованием большого
После пересмотра мы пришли к выводу, что временная сложность на самом деле равна O (2 ^ n)
Вопрос в том, что такое временная сложность? Это O (2 ^ n) или?
Я полагаю, что это связано с тем, что цикл for считается запущенным n раз. Тогда вложенный цикл while пробегает 2 ^ n времени. Второй цикл while работает 2 ^ n времени.
Algorithm subsetsGenerator(T)
Input: A set T of n elements
Output: All the subsets of T stored in a queue Q {
create an empty queue Q;
create an empty stack S;
let a1, a2, …, an be all the elements in T;
S.push({}); // Push the empty subset into the stack
S.push({a1})
for ( each element ai in T-{a1} )
{
while (S is not empty )
{
x=S.pop;
Q.enqueue(x);
x=x ∪ { ai };
Q.enqueue(x);
}
if ( ai is not the last element )
while (Q is not empty )
{
x=Q.dequeue();
S.push(x);
}
}
}
Изменить: Если вы хотите, чтобы я разбил анализ, прокомментируйте ниже.
Ответы
Ответ 1
Для вашего множества T из n элементов общее число подмножеств равно 2 ^ n. Если вы хотите сохранить все эти подмножества в Q, временная сложность не меньше O (2 ^ n).
На самом деле, я думаю, что O (2 ^ n) является ответом.
Если я правильно понимаю ваш алгоритм, вы пытаетесь сделать для каждого элемента a_i в T, вытащите все в S, верните его в S дважды - один раз без a_i и один раз с a_i.
Следовательно, общая временная сложность равна (1 + 2 + 4 +... + 2 ^ n) раз C, C означает время для pop, enqueue, dequeue и push, что является O (1). Термин выше равен 2 ^ (n + 1) -1, который все еще равен O (2 ^ n).