1

空間または時間の複雑さに合わせて最適化されたアルゴリズムを書く練習をしています。素数ふるいでは、少なくとも、見つかったすべての素数のリストを保存する必要があります。見つかった素数の数に比例するデータは、そのようなアルゴリズムが使用するスペースの最小量であるようです。

  • この根拠は有効ですか？
  • このアルゴリズムのスペースの複雑さはどのように評価されますか?

ウィキペディアからアトキンのふるいについて- 素数の数がこれを超えると、ふるいが O(n^1/2) スペースをどのように使用できるかがわかりません。これが、少なくとも空間が素数の数に比例しなければならないように思われる理由です。可算数と空間の複雑さを混同していませんか?

Atkin のふるいに関するこの論文では、彼らのアルゴリズムは「N までの素数を出力します...ここでの「メモリ」には、プリンターで使用される紙は含まれません。」これはスペースの不公平な計算のようです。

  • これがどのように測定されるべきか、実際に客観的に測定されているかを明確にしていただければ幸いです。
def prime_sieve(limit):
    factors = dict()
    primes = []
    factors[4] = (2)
    primes.append(2)
    for n in range(3, limit + 1):
        if n not in factors:
            factors[n * 2] = (n)
            primes.append(n)
        else:
            prime = factors.get(n)
            m = n + prime
            while m in factors:
                m += prime
            factors[m] = (prime)
            del factors[n]
    return primes
4

3 に答える 3

2

このアルゴリズムの空間複雑度はlen(numbers) + len(primes)です。リストのサイズに辞書のサイズを加えたもの。

この場合、単純な素数ふるい ( ) に対して予想されるよりもアルゴリズムが悪化limitしています。len(numbers) + len(primes) > limitたとえばprime_sieve(100)、次の無関係な番号が に格納されているためnumbersです。

{129: 43, 134: 67, 141: 47, 142: 71, 146: 73, 158: 79, 166: 83, 178: 89, 194: 97, 102: 17, 104: 2, 105: 3, 106: 53, 110: 11, 111: 37, 112: 7, 114: 19, 115: 23, 116: 29, 117: 13, 118: 59, 120: 5, 122: 61, 123: 41, 124: 31}

さまざまな時間と空間の複雑さを持ついくつかの素数ふるいがあります。たとえば、ウィキペディアと、エラトステネスのふるいの空間の複雑さを減らして a と b の間に素数を生成するにはどうすればよいですか?などの質問を参照してください。

また、必要がないことに注意してくださいprime = numbers.get(n)- あなたはすでにチェック済みif n not in numbersなので、そのまま使用できますprime = numbers[n]。

于 2014-10-20T10:15:29.753 に答える
1

" 素数ふるいでは、少なくとも、見つかったすべての素数のリストを保存する必要があります。"

正しくない。その範囲内の素数をふるいにかけるには、上限の平方根を下回る (および含む) 素数のみが必要です。

また、ふるいが増分的で無制限の場合、現在の生産点の平方根を下回る (および含む) 素数のみが必要です。

そんなことがあるものか？「コア」素数 (sqrt 未満のもの) に別の素数供給を使用することにより、同じ関数で再帰的に計算しても問題ありません。例については、この回答を参照してください。

そして、生成された素数を数えないことは完全に合法です-実際にそれらをプリンターや外部ファイルなどに送信できます。したがって、そのようなふるいのスペースの複雑さは、N ~= n * log nO( sqrt(N)/log(N) ) ~ O( sqrt( n/log(n) ))までのn 個の素数になります。 .

また、アトキンのふるいには近づかないでください。巷の噂では、適切に車輪を付けたエラトステネスのふるいを打ち負かすことは不可能です(この件については、GordonBGoodによる回答を検索してください)。

于 2014-10-20T21:25:34.603 に答える
1

スペースの複雑さの測定は完全に公平です。で置き換えprimes.append(n)、yield nコンシューマ ルーチンで素数をすべて保存せずに 1 つずつ処理する場合 (たとえば、特定のプロパティを持つ素数を見つける場合)、素数自体に必要なストレージ スペースは O(1) であり、単位は O(1) です。素数の数。

(は、呼び出し元に値を発行し、関数の状態を保存して再入力できるようにするコルーチンの一種であるgeneratoryieldを構築する Python の方法です。)

于 2014-10-20T11:07:42.467 に答える