algorithm - 为什么4钉汉诺塔的时间复杂度为0(2 ^ n/2)？

例如，如果我使用4个磁盘，则该问题应根据方程分3步解决。不过，我的要走9步为什么会这样？
考虑一下这里的代码

include <stdio.h>
void towerOfHanoi(int n, char from_rod, char to_rod,
                  char aux_rod1, char aux_rod2)
{
if (n == 0)
    return;
if (n == 1) {
    printf("\n Move disk %d from rod %c to rod %c",
                        n, from_rod, to_rod);
    return;
}

towerOfHanoi(n - 2, from_rod, aux_rod1, aux_rod2,
                                        to_rod);
printf("\n Move disk %d from rod %c to rod %c ",
                   n - 1, from_rod, aux_rod2);
printf("\n Move disk %d from rod %c to rod %c ",
                      n, from_rod, to_rod);
printf("\n Move disk %d from rod %c to rod %c ",
                   n - 1, aux_rod2, to_rod);
towerOfHanoi(n - 2, aux_rod1, to_rod, from_rod,
                                    aux_rod2);
}

// driver program
int main()
{
    int n = 4; // Number of disks

    // A, B, C and D are names of rods
towerOfHanoi(n, 'A', 'D', 'B', 'C');
return 0;
}

最佳答案

当你有4个钉，时间复杂度移动1个PEG将需要1的比较。
移动2个PEG的时间复杂度需要3个比较。
时间复杂度＝2×t（n-2）＋3，n>＝3
用代换法求解。
t（n）=2*t（n-2）+3，n>=3
=2^2T（n-4）+2*3+3=2^3T（n-6）+2^2*3+2*3+3等等。
对于第k次替换，
=2^（k/2）*T（n-k）+2^（k/2-1）*3++2^2*3+2*3+3----方程（1）
取n-k=2=>k=n-2
所以方程（1）变成
=2^（n/2-1）*3+2^（n/2-2）.3+…+2^2*3+2*3+3
=3{1.（2^（n/2）-1）}
=θ（2^（n/2））

关于algorithm - 为什么4钉汉诺塔的时间复杂度为0(2 ^ n/2)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49623663/