2

我试图找到能被每个整数 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

欢迎任何提示和建议！

4

1 回答 1

2

要对这个算法的渐近运行时间给出一个好的估计实际上并不容易。作为一个大概的估计，它可能略小于 n！（即非常慢）。问题很简单，答案随着 n 快速增长：它是小于 n 的素数的最高幂的乘积（对于 n=20，即 2^4 * 3^2 *5*7*11*13 *17*19=232792560)。当您检查所有数字直至答案时，您的运行时间显然比这更长（确定需要做多少工作）。

记忆在这里不相关，因为您的算法不是递归的。

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

于 2012-07-28T23:21:35.680 回答