Dzisiaj w klasie mój nauczyciel napisał na tablicy ten rekurencyjny algorytm czynnikowy:

int factorial(int n) {
   if (n == 1) 
       return 1;
   else 
       return n * factorial(n-1);
}

Powiedziała, że ​​ma kosztT(n-1) + 1.

Następnie metodą iteracyjną powiedziała toT(n-1) = T(n-2) + 2 = T(n-3) + 3 ... T(n-j) + j, więc algorytm zatrzymuje się, gdyn - j = 1, więcj = n - 1.

Potem zastąpiłaj wT(n-1) + 1i uzyskaneT(1) + n-1.

Powiedziała wprost, że za to n-1 = 2(log2n-1), więc koszt algorytmu jest wykładniczy.

Naprawdę straciłem dwa ostatnie kroki. Czy ktoś może mi to wyjaśnić?