python - 阶乘数字和谜题、时间复杂度调查

Question

您认为 foo 函数的时间复杂度是多少(相对于 n)？

DIGIT_FACTORIAL = [1]
for x in range(1, 10):
    DIGIT_FACTORIAL.append(DIGIT_FACTORIAL[x-1]*x)

def digit_factorial(x):
    return DIGIT_FACTORIAL[x]

def foo(number_of_digits):
    n = 10**number_of_digits
    i = n//9

    while i != sum(digit_factorial(int(x)) for x in str(i)) and i < n:
        i += 1

    if i < n:
        return i
    return None 

Answer 1

O(n log(n))

说明:

每个while循环从 111...1 == n/9 开始运行至n 。这意味着 while 循环运行 n*8/9次。 O(n * some_constant) == O(n)。

在每次迭代中，总和是 i 中所有数字的总和。 。有log10(n) - 1 i 中的数字。 O(log10(n) - 1) == O(log(n))。

嵌套两个使得O(n log(n))。

请注意，上述解释并未考虑到如果 i == sum(...) 则循环可能会提前中断。 。这是因为 sum(digit_factorial(int(x)) for x in str(i)) 的上限是 9! * number_of_digits它总是小于 i当number_of_digits大于7左右。