Złożoność algorytmu rekurencyjnego silni

Question

Dziś w klasie mój nauczyciel napisał na tablicy, to rekurencyjny algorytm silni:

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

Powiedziała, że ​​ma ona koszt T(n-1) + 1.

Następnie za pomocą metody iteracji powiedziała, że ​​T(n-1) = T(n-2) + 2 = T(n-3) + 3 ... T(n-j) + j, więc algorytm zatrzymuje się, gdy n - j = 1, czyli j = n - 1.

Następnie zastąpiła j w T(n-1) + 1 i uzyskała T(1) + n-1.

ona bezpośrednio, że w tym n-1 = 2 ^{(log n-1)}, więc koszt algorytmu jest wykładniczy.

Naprawdę straciłem dwa ostatnie kroki. Czy ktoś może mi je wytłumaczyć?

Answer 1

Zacznijmy od analizy tego algorytmu. Możemy napisać relację powtarzalności dla całkowitej ilości wykonanej pracy. W przypadku podstawowym, wykonać jedną jednostkę pracy, kiedy algorytm jest prowadzony na wejściu o rozmiarze 1, tak

T (1) = 1

na wejście wielkości n + 1 twój algorytm wykonuje jedną jednostkę pracy w samej funkcji, a następnie wywołuje tę samą funkcję na wejściu o rozmiarze n. Dlatego

T (n + 1) = T (n) + 1

Jeśli rozwinąć warunki nawrotu, to masz

• T (1) = 1
• T (2) = T (1) + 1 = 2
• T (3) = T (2) + 1 = 3
• T (4) = T (3) + 1 = 4
• ...
• T (n) = N

Ogólnie więc algorytm wymaga n jednostek pracy do wykonania (tzn T (n) = n).

Następną rzeczą, nauczyciel powiedział, że

T (n) = n = 2 ^{dziennika n}

To stwierdzenie jest prawdziwe, ponieważ 2 ^{dziennika x} = x dla dowolnego niezerowego x, ponieważ potęgowanie i logarytmy są operacjami odwrotnymi względem siebie.

Pytanie brzmi: czy jest to czas wielomianowy czy czas wykładniczy? Sklasyfikuję to jako czas pseudopolomianowy.Jeśli traktujesz wejście x jako liczbę, to środowisko wykonawcze jest rzeczywiście wielomianem wx. Jednak czas wielomianu jest formalnie określony tak, że czas wykonywania algorytmu musi być wielomianem w odniesieniu do liczby bitów użytych do określenia wejścia do problemu. Tutaj liczba x może być podana tylko w bitach Θ (log x), więc środowisko wykonawcze 2 ^{log x} jest technicznie uważane za czas wykładniczy. Napisałem o tym jako o długości w this earlier answer i polecam przyjrzenie się temu dokładniejszemu wyjaśnieniu.

Mam nadzieję, że to pomoże!