阶乘数字总和难题，时间复杂度调查
Factorial digits sum puzzle, time complexity survey
您认为 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
O(n log(n))
解释：
每个 while 循环从 111...1 == n/9 运行到 n。这意味着 while 循环运行 n*8/9 次。 O(n * some_constant) == O(n).
在每次迭代中，总和是在 i 中的所有数字。 i 中有 log10(n) - 1 个数字。 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，当 number_of_digits 大于 7 左右时，它总是小于 i。
您认为 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
O(n log(n))
解释：
每个 while 循环从 111...1 == n/9 运行到 n。这意味着 while 循环运行 n*8/9 次。 O(n * some_constant) == O(n).
在每次迭代中，总和是在 i 中的所有数字。 i 中有 log10(n) - 1 个数字。 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，当 number_of_digits 大于 7 左右时，它总是小于 i。