混淆数生成算法的Time Complexity分析（类DFS回溯实现）

问题背景 #

作为拍卖师，需打印编号1到upperBound的标牌，为避免翻转后无法识别，要标记所有混淆数。约束条件如下：

• 混淆数字仅包含0、1、6、8、9
• 数字不能有前导零

算法优化历程 #

• 初始实现暴力线性解法
• 用集合优化后工作量减半，但仍为线性复杂度
• 最终优化：将数字视为以数位为分支的树，实现类回溯方案（对应代码第25/26行和35/36行），可跳过范围内大量无效区间

核心困惑 #

无法准确描述该优化后算法的时间复杂度。通过统计flipNumber函数中while循环的执行次数来衡量整体工作量，发现其呈现分形模式，不知如何进行分析。

实现代码 #

class Solution:
    def __init__(self, upperBound: int) -> None:
        self.confusing = {
            0: 0,
            1: 1,
            6: 9,
            8: 8,
            9: 6,
        }
        self.loops = 0
        self.upperBound = upperBound
        self.answer = self.generateConfusingNumbers()
    def generateConfusingNumbers(self) -> set:
        answer = set()
        if self.upperBound >= 9:
            answer.update([6, 9])
        i = 15
        while i <= self.upperBound:
            i += 1
            if not i % 10 or i in answer:
                continue
            flipped = self.flipNumber(i)
            if flipped[0] and i != flipped[0] and flipped[0] <= self.upperBound:
                answer.update([i, flipped[0]])
            elif not flipped[0]:
                i += (10 ** (flipped[1] - 1)) - 1
        return answer
    def flipNumber(self, number: int) -> tuple:
        answer = 0
        digCount = 0
        while number > 0:
            self.loops += 1
            number, digit = divmod(number, 10)
            digCount += 1
            if digit not in self.confusing:
                return (None, digCount)
            digit = self.confusing[digit]
            answer = answer * 10 + digit
        return (answer, digCount)
    def printAnswer(self):
        print(len(self.answer))
        print(self.answer)
    def printWork(self):
        print(self.upperBound, self.loops)

运行数据说明 #

• 100-10000次运行工作量：展示100到10000次运行的工作量情况
• 6000-7000次运行情况：展示6000到7000次运行的细节表现
• 优化版与原版对比：对比优化后代码与原始代码的工作量差异

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