Python 3两段代码时间复杂度差异及性能问题咨询

核心优化方向：反向推导替代正向搜索 #

你遇到的性能差异本质是算法思路的问题。正向用BFS/递归的话，每次操作会生成两个新数值，当b很大时，分支会指数级膨胀，时间复杂度接近O(b)，必然超时。而反向推导的话，从b倒推回a，每次最多只有1-2种合法操作，时间复杂度是O(log b)，效率直接拉满。

具体实施步骤 #

• 先处理边界：如果a > b，直接返回-1；a等于b的话返回0。
• 从b开始循环反向推导：
  • 若b的末位是1，说明只能通过10x+1操作得到，所以把b改成(b-1)//10，操作次数加1。
  • 若b是偶数，尝试把b除以2，操作次数加1；如果b既不是偶数也末位不为1，直接返回-1（没有合法操作能得到当前b）。
• 循环结束后，检查最终的b是否等于a：相等就返回操作次数，否则返回-1。

代码A超时原因排查 #

代码A大概率用了正向搜索思路（比如BFS、递归），需要检查这几点：

• 有没有记录已访问的数值？如果没有，同一数值会被反复处理，浪费大量时间。
• 有没有设置合理的终止条件？比如生成的数值超过b还继续处理，完全没必要。
• 是不是递归深度太大导致栈溢出或者重复计算？

参考代码片段 #

def min_steps(a, b):
    steps = 0
    while b > a:
        if b % 10 == 1:
            b = (b - 1) // 10
            steps += 1
        elif b % 2 == 0:
            b //= 2
            steps += 1
        else:
            return -1
    return steps if b == a else -1

内容的提问来源于stack exchange，提问作者Lina