Анализ временной сложности с использованием большого

После пересмотра мы пришли к выводу, что временная сложность на самом деле равна 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).