代码之家 › 专栏 › 技术社区 › cglacet

阶乘数字和谜,时间复杂性调查

asymptotic-complexity time-complexity python-3.x python

cglacet · 技术社区 · 8 年前

你认为时间复杂度如何? 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

1 回复 | 直到 8 年前

Ben Jones Tim Goetz 8 年前

O(n对数(n))

说明:

每 while 循环从 111...1 == n/9 到 n . 这意味着while循环运行 n*8/9 时代。O(n*某个常数)== O(n) .

在每次迭代中,总和在 i . 有 log10(n) - 1 数字输入 我 . O(对数10(n)-1)== O(对数(n)) .

把这两个做窝 O(n对数(n)) .

注意,上面的解释没有考虑到如果 i == sum(...) . 那是因为 sum(digit_factorial(int(x)) for x in str(i)) 是 9! * number_of_digits 它总是小于 我 什么时候 number_of_digits 大于7左右。

推荐文章

ÎÎÎ½Î· ÎÎ®Î¹Î½Î¿Ï · Python lxml.html语法错误:使用lxml find时XPATH的谓词无效

1 年前

Cam · Pandas列表日期到日期时间

1 年前

RASEL MAHMUD · 为什么以及如何在is_even()函数内的IF条件中递归X变量在满足0后递增?[副本]

1 年前

jjkennedy · Pandas文本文件导入:当每个文件中存在多个表时,自动选择1个表

1 年前

LMC · Numpy数组布尔索引以获取包含元素

1 年前

vr8ce · 非成对标记中特定字符的正则表达式

1 年前

Kernel · 如果指定了crs参数,shapefile的geopandas.read_file将出错

1 年前

ShaAnder · 为什么sqllachemy返回的是类而不是字符串

1 年前

sixtytrees · detectron2软件包未安装(没有名为“torch”的模块),但我安装了torch

1 年前

Pernoctador · Python映射可以复制吗?我需要参考地图

1 年前