Hanoi Kulesi Algoritması ve 2^n Karmaşıklığı

Bu program, ünlü "Hanoi Kuleleri" problemini çözmek için gerekli tüm hareketleri yazdırır.

void solve_hanoi (int N, string from_peg, string to_peg, string spare_peg)

{

if (N<1) {

return;

}

if (N›1) {

solve_hanoi(N-1, from_peg, spare_peg, to_peg);

}

print “move from " + from_peg + “ to " + to_peg;

if (N›1) {

solve_hanoi(N-1, spare_peg, to_peg, from_peg);

}

}

T (N) N tane eleman için gereken süredir.

Sahibiz:

T(1) = O(1)

ve

T(N) = O(1) + 2*T(N-1) N›1 olduğu sürece

Son terimi tekrar tekrar genişletirseniz, şunları elde edersiniz:

T(N) = 3*O(1) + 4*T(N-2)

T(N) = 7*O(1) + 8*T(N-3)

...

T(N) = (2^(N-1)-1)*O(1) + (2^(N-1))*T(1)

T(N) = (2^N - 1)*O(1)

T(N) = O(2^N)

https://stackowerflow.com/questions/34915869/examp1e_of_big_o_of_2n