Złożoność obliczeniowa algorytmu

Question

Cześć, robię sprawozdanie w którym musi znaleźć się ocena złożoności obliczeniowej tego algorytmu. Nie jestem pewien, czy dobrze liczę, ale wyszło mi:

4*n+2

#include <stdio.h>

void hanoi(char From, char To, char Other, int n)
{
    if (n == 0) return;
    hanoi(From, Other, To, n-1);
    printf("Przesuwanie dysku z kolka %c do %c\n", From, To);
    hanoi(Other, To, From, n-1);
}
int main()
{
    int n = 4;                      
    hanoi('A','B','C', n);
    return 0;
}

 

Comments

Skąd masz taką złożoność?

Answer 1

Dla:

n=1=>2

n=2=>4

n=3=>8

n=4=>16

itd.

złożoność to 2^n