python - Big-O标记和优化功能以包括备忘录？

Question

我正在尝试找到可被每个1-20（含）整数平均除的最小数。这只是我试图改进以前做过的练习。

我编写了一个函数，该函数接受一个参数并返回最小的数字，该最小数字可被每个小于参数（包括其自身）的正整数均分的整数，但是它没有经过优化，并且随着数字变大而运行相对较慢。

我想知道此功能的Big-O表示法是什么以及为什么。然后，如果有的话，有没有办法加快这一步，也许我不确定是否有备忘录？

def divide_by_all(x):
    ## the 'pos' variable will be matched up against the argument to keep track of how many of the numbers in ##
    ## the arguments range are dividing evenly. ##
    pos = 0
    ## the 'count' variable will be set to equal the input argument, possibly
    count = x
    ## create the range of integers for the argument ##
    divs = [i for i in range(1,x + 1)]
    while pos != x:
        for i in divs:
            ## check if each 'i' in the divs list is evenly divisible ##
            ## if 'i' is not evenly divisible the 'count'(answer) is incremented, the 'pos' is set back to zero to show ##
            ## the next 'count' has no evenly divisible in numbers div yet, and then loop over the divs list starts again ##
            if count % i != 0:
                count += 1
                pos = 0
                break
            ## if 'i' is evenly divides into current 'count' increment 'pos' ##
            if count % i == 0:
                pos += 1
            ## if 'pos' == the argument 'x', meaning every number in range(x) is evenly divisible ##
            ## return 'count' ##
            if pos == x:
                return count

欢迎任何提示和建议！

Answer 1

估计此算法的渐近运行时间实际上并不容易。据估算，它可能小于n！ （即非常慢）。问题很简单，答案是随着n迅速增长：它是素数小于n的最高幂的乘积（对于n = 20，这将是2 ^ 4 * 3 ^ 2 * 5 * 7 * 11 * 13 * 17 * 19 = 232792560）。当您检查所有数字直到答案时，您的运行时间显然比那还要长（确定需要多少时间才能完成工作）。

由于您的算法不是递归的，因此此处的备注不相关。

基本上，这是一个数学问题，而不是算法问题。