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

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

Ответ 1

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

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

Возьмем 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}

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

Но вы также должны искать серый код.

Ответ 2

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

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

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

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

Ответ 3

Quantum Bogosort имеет пространственную сложность 2 ^ n.

Ответ 4

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

Ответ 5

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

написано в java
похоже, не могут заставить вкладки работать базовая операция - я ++;

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);  
     }
}