Пример Big O of 2 ^ n

Итак, я могу представить, какой алгоритм имеет сложность n ^ c, просто количество вложенных циклов.

for (var i = 0; i < dataset.len; i++ {
    for (var j = 0; j < dataset.len; j++) {
        //do stuff with i and j
    }
}

Лог - это то, что разбивает набор данных пополам каждый раз, двоичный поиск делает это (не совсем уверен, какой код для этого выглядит).

Но что такое простой пример алгоритма, который является c ^ n или, более конкретно, 2 ^ n. Является ли O (2 ^ n) на основе циклов через данные? Или как данные разделяются? Или что-то еще?

Ответ 1

Алгоритмы с временем работы O (2 ^ N) часто являются рекурсивными алгоритмами, которые решают проблему размера N рекурсивным решением двух меньших задач размера N-1.

Эта программа, например, распечатывает все ходы, необходимые для решения знаменитой проблемы "Башни Ханоя" для N дисков в псевдокоде

void solve_hanoi(int N, string from_peg, string to_peg, string spare_peg)
{
    if (N<1) {
        return;
    }
    if (N>1) {
        solve_hanoi(N-1, from_peg, spare_peg, to_peg);
    }
    print "move from " + from_peg + " to " + to_peg;
    if (N>1) {
        solve_hanoi(N-1, spare_peg, to_peg, from_peg);
    }
}

Пусть T (N) - время, необходимое для N дисков.

Имеем:

T(1) = O(1)
and
T(N) = O(1) + 2*T(N-1) when N>1

Если вы повторно используете последний термин, вы получаете:

T(N) = 3*O(1) + 4*T(N-2)
T(N) = 7*O(1) + 8*T(N-3)
...
T(N) = (2^(N-1)-1)*O(1) + (2^(N-1))*T(1)
T(N) = (2^N - 1)*O(1)
T(N) = O(2^N)

Чтобы понять это, вам просто нужно знать, что определенные закономерности в рекуррентном отношении приводят к экспоненциальным результатам. Обычно T(N) = ... + C*T(N-1) с C > 1 означает O (x ^ N). См:

https://en.wikipedia.org/wiki/Recurrence_relation

Ответ 2

Подумайте, например. итерации по всем возможным подмножествам множества. Такие алгоритмы используются, например, для обобщенной задачи о ранце.

Если вам трудно понять, как итерация над подмножествами переводится на O (2 ^ n), представьте себе набор из n переключателей, каждый из которых соответствует одному элементу набора. Теперь каждый из переключателей можно включить или выключить. Подумайте о "on" как о подмножестве. Обратите внимание, сколько комбинаций возможно: 2 ^ n.

Если вы хотите увидеть пример кода, обычно проще подумать о рекурсии, но я не могу представить ни одного другого приятного и поддающегося пониманию примера прямо сейчас.

Ответ 3

  int Fibonacci(int number)
 {
  if (number <= 1) return number;

  return Fibonacci(number - 2) + Fibonacci(number - 1);
 }

Рост увеличивается с каждым дополнением к набору входных данных. Кривая роста функции O (2N) экспоненциальна - начинается очень мелко, а затем растет метеоритно. Мой пример большой O (2 ^ n), но гораздо лучше:

public void solve(int n, String start, String auxiliary, String end) {
   if (n == 1) {
       System.out.println(start + " -> " + end);
   } else {
       solve(n - 1, start, end, auxiliary);
       System.out.println(start + " -> " + end);
       solve(n - 1, auxiliary, start, end);
   }

В этом методе программа печатает все ходы для решения проблемы "Башня Ханоя". Оба примера используют рекурсивную задачу для решения проблемы и имеют большое время работы O (2 ^ n).

Ответ 4

c ^ N = Все комбинации элементов n от алфавита размером c.

Более конкретно, 2 ^ N - все числа, представимые с N битами.

Общие случаи реализуются рекурсивно, например:

vector<int> bits;
int N
void find_solution(int pos) {
   if (pos == N) {
     check_solution();
     return;
   }
   bits[pos] = 0;
   find_solution(pos + 1);
   bits[pos] = 1;
   find_solution(pos + 1);
}