汉诺塔问题迭代算法的时间复杂度和Space复杂度？

Question

我无法使用迭代算法找到汉诺塔问题的时间复杂度和 Space 复杂度。有人可以帮忙吗？

迭代算法：

计算所需的移动总数，即“pow(2, n) - 1”，这里 n 是磁盘数。
如果磁盘数（即 n）为偶数，则交换目标极和辅助极。
对于 i = 1 到移动总数：如果我 %3 == 1: 源极和之间顶盘的合法移动目的地杆如果我 %3 == 2: 源极和之间的合法运动顶盘辅助杆
如果我 %3 == 0: 副极间合法移动顶盘和目的地杆

代码-

// C Program for Iterative Tower of Hanoi
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>

// A structure to represent a stack
struct Stack
{
unsigned capacity;
int top;
int *array;
};

// function to create a stack of given capacity.
struct Stack* createStack(unsigned capacity)
{
    struct Stack* stack =
        (struct Stack*) malloc(sizeof(struct Stack));
    stack -> capacity = capacity;
    stack -> top = -1;
    stack -> array =
        (int*) malloc(stack -> capacity * sizeof(int));
    return stack;
}

// Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{
return (stack->top == stack->capacity - 1);
}

// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{
return (stack->top == -1);
}

// Function to add an item to stack. It increases
// top by 1
void push(struct Stack *stack, int item)
{
    if (isFull(stack))
        return;
    stack -> array[++stack -> top] = item;
}

// Function to remove an item from stack. It
// decreases top by 1
int pop(struct Stack* stack)
{
    if (isEmpty(stack))
        return INT_MIN;
    return stack -> array[stack -> top--];
}

//Function to show the movement of disks
void moveDisk(char fromPeg, char toPeg, int disk)
{
    printf("Move the disk %d from \'%c\' to \'%c\'\n",
        disk, fromPeg, toPeg);
}

// Function to implement legal movement between
// two poles
void moveDisksBetweenTwoPoles(struct Stack *src,
            struct Stack *dest, char s, char d)
{
    int pole1TopDisk = pop(src);
    int pole2TopDisk = pop(dest);

    // When pole 1 is empty
    if (pole1TopDisk == INT_MIN)
    {
        push(src, pole2TopDisk);
        moveDisk(d, s, pole2TopDisk);
    }

    // When pole2 pole is empty
    else if (pole2TopDisk == INT_MIN)
    {
        push(dest, pole1TopDisk);
        moveDisk(s, d, pole1TopDisk);
    }

    // When top disk of pole1 > top disk of pole2
    else if (pole1TopDisk > pole2TopDisk)
    {
        push(src, pole1TopDisk);
        push(src, pole2TopDisk);
        moveDisk(d, s, pole2TopDisk);
    }

    // When top disk of pole1 < top disk of pole2
    else
    {
        push(dest, pole2TopDisk);
        push(dest, pole1TopDisk);
        moveDisk(s, d, pole1TopDisk);
    }
}

//Function to implement TOH puzzle
void tohIterative(int num_of_disks, struct Stack
            *src, struct Stack *aux,
            struct Stack *dest)
{
    int i, total_num_of_moves;
    char s = 'S', d = 'D', a = 'A';

    //If number of disks is even, then interchange
    //destination pole and auxiliary pole
    if (num_of_disks % 2 == 0)
    {
        char temp = d;
        d = a;
        a = temp;
    }
    total_num_of_moves = pow(2, num_of_disks) - 1;

    //Larger disks will be pushed first
    for (i = num_of_disks; i >= 1; i--)
        push(src, i);

    for (i = 1; i <= total_num_of_moves; i++)
    {
        if (i % 3 == 1)
        moveDisksBetweenTwoPoles(src, dest, s, d);

        else if (i % 3 == 2)
        moveDisksBetweenTwoPoles(src, aux, s, a);

        else if (i % 3 == 0)
        moveDisksBetweenTwoPoles(aux, dest, a, d);
    }
}

// Driver Program
int main()
{
    // Input: number of disks
    unsigned num_of_disks = 3;

    struct Stack *src, *dest, *aux;

    // Create three stacks of size 'num_of_disks'
    // to hold the disks
    src = createStack(num_of_disks);
    aux = createStack(num_of_disks);
    dest = createStack(num_of_disks);

    tohIterative(num_of_disks, src, aux, dest);
    return 0;
}

汉诺塔迭代算法代码如上。请帮帮我。

Answer 1

我们定义为圆盘数。

时间复杂度为 O(2)，因为这是在代码中出现的唯一循环中完成的迭代次数，而所有其他代码都以恒定时间运行。

space 复杂性可以分为两部分：

“塔”本身（堆栈）具有 O() space 复杂度
auxiliary space 的复杂度为 O(1) space，因为没有其他向量，并且调用堆栈具有固定大小（没有动态递归）

所以结合起来有一个 O() space 复杂度。

Answer 2

这取决于，因为这个问题从根本上是模棱两可的。汉诺塔算法最有趣的地方在于它是一个伪随机无理结构，具有指数信息，但是如果将塔从左向右移动，然后再从右向左移动，时间复杂度正好是 0.

例如，没有可以计算 5 的平方根的快速算法。

这意味着这个问题基本上是主观的，取决于你所说的河内塔的含义以及你真正想要提取的信息量。

汉诺塔问题迭代算法的时间复杂度和Space复杂度？

Time Complexity and Space Complexity of Tower of Hanoi problem iterative algorithm?

algorithm

time-complexity

space-complexity

towers-of-hanoi