2 ^ n алгоритм сложности

Question

Мне нужно реализовать и протестировать алгоритм со сложностью 2 ^ n.Я пытался найти один на некоторое время.Если есть какой-то способ, я могу добиться этого путем реализации - с точной сложностью 2 ^ n, что было бы оптимальным.Если кто-нибудь знает место, я могу найти пример или помочь мне его реализовать, это было бы здорово :-).Базовая операция может быть чем угодно, но только одним оператором, таким как i ++;было бы лучше.

Answer 1

Создать все подмножества набора с n элементами.

Добавлено.Самым простым способом генерации всех подмножеств S = {a0, a1, ..., an-1} является, вероятно, перевод между двоичным представлением ранга и подмножеством.

Take S = {a0, a1, a2}.

rank binary subset
0    000    {} 
1    001    {a0}
2    010    {a1}
3    011    {a0, a1}
4    100    {a2}
5    101    {a0, a2}
6    110    {a1, a2}
7    111    {a0, a1, a2}

Итак, 1 в двоичном виде означает, что соответствующий элемент находится в подмножестве.0 означает, что элемент отсутствует в подмножестве.

Но вам также следует поискать код Грея.

Answer 2

Классический рекурсивный расчет числа Фибоначчи - O (2 ^ n).

unsigned Fib(unsigned n)
{
    if (n <= 1)
        return n;
    else
        return Fib(n - 1) + Fib(n - 2);
}

---

Поскольку приведенное выше на самом деле является тэтой (Phi ^ n), я добавляю тэта (2 ^ n) алгоритм, который возвращает 2 ^ n. Спасибо Иеремии Уилкоку.

unsigned TwoExp(unsigned n)
{
    if (n == 0)
        return 1;
    else
        return TwoExp(n - 1) + TwoExp(n - 1);
}

Answer 3

Квантовый Богосорт имеет 2 ^ n пространственной сложности.

Answer 4

Я потратил много времени на переосмысление проблемы и хотел бы опубликовать решение, которое я нашел Все ответы способствовали моей способности придумать это решение, и я очень благодарен всем, кто ответил. :-) Я понимаю, что алгоритм практически ничего не делает.

написано в Java
не получается заставить работать вкладки
основная операция - это i ++;

public class TwoToTheN
{  
     private static int twoToTheN = 0;  
     private static int power = 3;

     public static void main(String[] args)   
     {  
         twoToTheN(power);  
         System.out.println(twoToTheN);  
     }  

     private static void twoToTheN(int n)  
     {  
         if(n == 0)   
         {  
             twoToTheN++;  
             return;  
         } 
         else if(n == 1)  
         {  
             twoToTheN++;  
             twoToTheN++;  
             return;  
         }  
         twoToTheN(n-1);  
         twoToTheN(n-1);  
     }
}  

Answer 5

Вот один: выведите цифры 2 ^ (2 ^ n).