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 に答える