Сложность времени для конкретной функции big-O

Question

Я заранее извиняюсь, если об этом ответили ранее.

Я понимаю, что временная сложность следующего кода O (п!):

void permutations(int n){ 
    if(n!=0){ 
    for(int i=0; i<n; i++){ 
     permutations(n-1); 
    }//for 
    }//if 
}//permutations 

Также я понимаю, что временная сложность следующего кода O (2^п) :

void permutations(int n){ 
    if(n!=0){ 
    permutations(n-1); 
    permutations(n-1); 
    }//if 
}//permutations 

Однако у меня возникли проблемы определения того, что сложность следующего кода, я подозреваю, что это O ((п^2) * (п)!), бу Я не уверен, что это правильно. Я был бы признателен, если бы кто-нибудь мог объяснить, прав ли я и почему.

void permutations(int n){ 
    if(n!=0){ 
    for(int i=0; i<n; i++){ 
     permutations(n-1); 
     permutations(n-1); 
    }//for 
    }//if 
}//permutations 

Answer 1

Я считаю, что вы имели в виду опечатку и O ((2^п) * (п!)), что ответ.

подход Непрофессионала:

Без этого доказательства (я немного ржавый себя), рассмотрим п = 4:

• при п = 4, цикл 4 раза, каждый итерационный вызов permutations(3) дважды. Итак, всего 4 x 2 = 8 звонков.

• При n = 3 мы выполняем 3 раза, каждая итерация вызывает permutations(2) дважды, но при n = 4 мы сделали 8 таких вызовов. Итак, всего 3 x 2 x 8 = 48 звонков.

• При n = 2, мы повторяем 2 раза, каждая итерация вызывает permutations(1) дважды, но при n = 3 мы сделали 48 таких вызовов. Итак, всего 2 x 2 x 48 = 192 звонка.

• При n = 1 мы выполняем цикл 1 раз, каждая итерация вызывает permutations(0) дважды, но при n = 2 мы сделали 192 таких вызова. Итак, всего 1 x 2 x 192 = 384 звонка.

• Мы не заботимся о n = 0, так как это базовый корпус.

Исследование роста рекурсии, у нас есть один вызов permutations(4) растет до 384 вызовов. Работая в обратном направлении от этой фигуры:

• 384 == 1 х 2 х 192

• 1 х 2 (2 х 2 х 48)

• ...

• 1 х 2 х (2 х 2 х (3 х 2 х (4 х 2)))

• 2 х 2 х 2 х 2 х 4 х 3 х 2 х 1

• 2^4 x 4!

Похоже, мы можем сделать вывод, что O ((2^п) * (п!)).

---

Решение рекуррентных соотношений:

Теперь, когда я пересмотренные решения рекуррентных отношений с использованием Big-Oh for Recursive Functions: Recurrence Relations из Университета Дьюка, адаптируя подход к этой проблеме:

• Пусть Т (п) время для выполнения permutations(n) и T (0) = 1.
• Мы знаем, что T (n) = nx 2 x T (n-1)
  • Это потому, что цикл n раз, выполнить перестановки (n-1) дважды.
• Т (п) = NX 2 х ((п-1) х 2 х Т (N-2))
• Т (п) = NX 2 х ((п-1) х 2 х ((n-2) x 2 x T (n-3)))
• Таким образом, мы можем обобщить это для k разложений при T (n) = 2^k * k!
  • Мы можем наблюдать коэффициенты n, n-1, n-2, ..., 1 (в базовом случае), это факторная составляющая (k!).
  • При каждом расширении мы имеем дополнительный коэффициент 2, таким образом, 2^k.
• В качестве базового случая п = 0, мы имеем к = п

Таким образом O ((2^п) * (п!)).