1 条题解

  • 0
    @ 2025-7-31 15:49:58
    汉诺塔递归算法的时间复杂度是 O(2ⁿ),其中 n 是盘子的数量。
    原因分析:
    汉诺塔问题的递归解法遵循以下逻辑:
    
    将 n-1 个盘子从源柱移动到辅助柱(需要 T(n-1) 次操作)
    将第 n 个盘子从源柱移动到目标柱(1 次操作)
    将 n-1 个盘子从辅助柱移动到目标柱(又需要 T(n-1) 次操作)
    
    因此,递归公式为:
    T(n) = 2*T(n-1) + 1(边界条件:T(1) = 1)
    
    通过展开公式可得:
    T(n) = 2ⁿ - 1
    
    
    • 1

    信息

    ID
    671
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    5
    已通过
    2
    上传者