Пример итеративного алгоритма O (2 ^ n)

Question

Как видно из названия, что является примером итеративного O (2 ^ n) al go? Когда это обычно происходит?

Answer 1

Ханойская башня может быть хорошим примером.

Ханойская башня состоит из трех стержней или колышков с n дисками, расположенными один над другим.

Цель головоломки - переместить весь стек в другой жезл, следуя этим 3 правилам.

1. Одновременно можно перемещать только один диск. 2. Каждый ход состоит в том, чтобы взять верхний диск из одной стопки и поместить его поверх другой стопки или на пустой стержень. 3. Ни один большой диск не может быть помещен поверх меньшего диска.

Минимальное количество ходов, необходимое для решения головоломки Ханойской башни, составляет 2 ^ n - 1, где n - количество дисков.

https://en.wikipedia.org/wiki/Tower_of_Hanoi#Iterative_solution

Answer 2

Эта ссылка объясняет это лучше, но алгоритм с порядком O (2 ^ n) обычно является жадным алгоритмом. Самый жадный из всех, кого я знаю, это O (n ^ n). Алгоритм восстановления Фибоначчи, без использования метода запоминания значений, является примером алгоритма O (2 ^ n).

пример (python)

def fib(n):
    if n == 0: return 1
    if n == 1: return 1
    return fib(n-1) + fib(n-2)

В строке 4 мы есть, что функция вызывается дважды. Это означает, что итеративный метод будет вызываться 2 раза за каждый вызов.

---

Для чего-то строго итеративного вы можете рассмотреть пример (код в python):

def O2n(n):
    a = 0
    while True:
        if a < 2**n:
            a = a + 1
        else:
            break
    return a

В коде я заставляю алгоритм быть O (2 ^ n) через условие. Это не практический пример, но с помощью условия можно получить алгоритмы другого порядка.