确定算法的时间复杂度（DFS？排序？）

Question

我最近遇到了以下问题： 你是一名拍卖师，你需要打印从 1 到 upperBound 编号的标志。您担心某些标志可能会被翻转并变得无法辨认，因此您决定在每个可能令人困惑的数字下划线。
编写将生成所有令人困惑的数字的代码。

约束条件：

• 令人困惑的数字：0、1、6、8、9
• 没有数字会有前导零

我首先想出了一个蛮力，线性的解决方案，然后决定优化它。 首先，我使用一个集合将我的工作减半，但这仍然是一个线性问题。 通过将其视为一棵树，每个数字都是一个分支，我能够实现某种回溯解决方案（第 25/26 和 35/36 行），这使我能够跳过范围内的巨大差距。

不过，我不知道如何描述时间复杂度。为了对其进行测量，我计算了 flipNumbers 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)

展示工作的图表：