2

私はHaskellで問題3に次の解決策を持っています:

isPrime :: Integer -> Bool
isPrime p = (divisors p) == [1, p]

divisors :: Integer -> [Integer]
divisors n = [d | d <- [1..n], n `mod` d == 0]

main = print (head (filter isPrime (filter ((==0) . (n `mod`)) [n-1,n-2..])))
  where n = 600851475143

ただし、Project Euler で指定された分の制限よりも多くかかります。では、コードの時間の複雑さを分析して、どこを変更する必要があるかを判断するにはどうすればよいでしょうか?

注:代替アルゴリズムを投稿しないでください。それらを自分で解決したい。今のところ、自分が持っているコードを分析して、それを改善する方法を探したいだけです。ありがとう！

4

3 に答える 3

11

2つのこと：

  1. divisorsリスト内包表記 ( にあるように)、または同等に、リストに対するいくつかの一連のmapand/orfilter関数 ( にあるように)を見るときはいつでもmain、その複雑さを を扱うのと同じように Θ(n) として扱います。for-命令型言語でのループ。

  2. これはおそらくあなたが期待していたようなアドバイスではありませんが、より役立つことを願っています: Project Euler の目的の一部は、さまざまな数学的概念の定義と、さまざまなアルゴリズムを使用するさまざまなアルゴリズムについて考えるように促すことです。これらの定義を正しく満たしている可能性があります。

さて、その2番目の提案は少し漠然としていました...たとえば、あなたが実装した方法isPrimeは実際には教科書の定義です:

isPrime :: Integer -> Bool
isPrime p = (divisors p) == [1, p]
-- p is prime if its only divisors are 1 and p.

同様に、 の実装divisorsは簡単です。

divisors :: Integer -> [Integer]
divisors n = [d | d <- [1..n], n `mod` d == 0]
-- the divisors of n are the numbers between 1 and n that divide evenly into n.

これらの定義はどちらも非常に読みやすいです! 一方、アルゴリズム的には、あまりにもナイーブです。簡単な例を見てみましょう: 数 10 の約数は何ですか? [1, 2, 5, 10]. 調べてみると、おそらくいくつかのことに気付くでしょう。

  • 1 と 10 はペア、2 と 5 はペアです。
  • 10 自体を除けば、10 の約数で 5 より大きいものは存在しません。

おそらく、これらのようなプロパティを利用してアルゴリズムを最適化できますよね? したがって、コードを見ずに (紙と鉛筆だけを使って) のより高速なアルゴリズムをスケッチしてみてくださいdivisors。あなたが私のヒントを理解していればdivisors n、間に合うはずsqrt nです。続行すると、これらの線に沿ってさらに多くの機会が見つかります。関数をまったく使用しない方法で、すべてを別の方法で再定義することにするかもしれませんdivisors...

これが、これらの問題に取り組むための正しい考え方を与えるのに役立つことを願っています!

于 2012-07-26T05:18:07.127 に答える
8

上から始めましょう。

divisors :: Integer -> [Integer]
divisors n = [d | d <- [1..n], n `mod` d == 0]

ここでは、特定のものは安価であると仮定しましょう: 数値の増分は O(1)、mod操作の実行は O(1)、および比較0は O(1) です。(これらは誤った仮定ですが、一体何なのですか。)関数は からまでdivisorsのすべての数値をループし、各数値に対して O(1) 演算を実行するため、完全な出力の計算は O(n) になります。ここで O(n) と言うとき、n は入力のサイズではなく、入力の数値であることに注意してください! n を格納するには m=log(n) ビットかかるため、この関数は入力のサイズで O(2^m) 時間かけて完全な答えを生成します。以下では、入力数と入力サイズを意味するために、一貫して n と m を使用します。1n

isPrime :: Integer -> Bool
isPrime p = (divisors p) == [1, p]

最悪の場合pは素数であり、divisors出力全体を強制的に生成します。静的に既知の長さのリストとの比較は O(1) であるため、これは への呼び出しによって支配されdivisorsます。O(n)、O(2^m)

あなたのmain関数は一度に多くのことを行うので、部分式を少し分解してみましょう。

filter ((==0) . (n `mod`))

これはリストをループし、各要素に対して O(1) 操作を行います。これは O(m) です。ここで、m は入力リストの長さです。

filter isPrime

リストをループし、各要素に対して O(n) の作業を行います。ここで、n はリスト内の最大数です。リストがたまたま n 要素の長さである場合 (あなたの場合のように)、これは O(n*n) 作業、または O(2^m*2^m) = O(4^m) 作業(上記のように、この分析はリスト全体を生成する場合のものです)。

print . head

ちょっとした作業。印刷部分を O(m) としましょう。

main = print (head (filter isPrime (filter ((==0) . (n `mod`)) [n-1,n-2..])))

上記のすべての部分式を考慮すると、filter isPrimeビットが明らかに支配的な要素です。O(4^m)、O(n^2)

ここで、考慮すべき最後の微妙な点が 1 つあります。上記の分析全体を通して、各関数/部分式がその出力全体を生成するように強制されているという仮定を一貫して行ってきました。でわかるようにmain、これはおそらく正しくありません。 を呼び出しますがhead、これはリストのほんの一部を強制するだけです。ただし、入力数値自体が素数でない場合は、少なくともリストの半分を調べなければならないことが確実にわかっています。 と の間n/2に約数はありませんn。したがって、せいぜい作業を半分に削減するだけで、漸近コストには影響しません。

于 2012-07-26T03:28:12.550 に答える
2

ダニエル・ワグナーの答えは、ランタイムの複雑さの境界を導き出す一般的な戦略をかなりうまく説明しています。ただし、一般的な戦略の場合によくあることですが、あまりにも控えめな境界が生成されます。

せっかくなので、この例をもう少し詳しく調べてみましょう。

main = print (head (filter isPrime (filter ((==0) . (n `mod`)) [n-1,n-2..])))
    where n = 600851475143

(余談:n素数の場合、 をチェックするときに実行時エラーが発生するためn `mod` 0 == 0、リストを に変更し[n, n-1 .. 2]て、アルゴリズムがすべての に対して機能するようにしますn > 1。)

式を部分に分割して、各部分をより簡単に確認して分析できるようにしましょう

main = print answer
  where
    n = 600851475143
    candidates = [n, n-1 .. 2]
    divisorsOfN = filter ((== 0) . (n `mod`)) candidates
    primeDivisors = filter isPrime divisorsOfN
    answer = head primeDivisors

ダニエルのように、私は算術演算、比較などは O(1) であるという仮定で作業します。真実ではありませんが、それはすべてのリモートで妥当な入力の十分な近似値です。

したがって、リストのうち、下candidatesからn下の要素answerを生成する必要があります。n - answer + 1要素の合計コストはO(n - answer + 1)です。複合nの場合、 がありanswer <= n/2、それが Θ(n) です。

必要に応じて除数のリストを生成することΘ(n - answer + 1)も同様です。

d(n)の約数についてはn、粗い推定値 を使用できますd(n) <= 2√n。

のすべての約数>= answerはn、素数性をチェックする必要があります。これは、すべての約数の少なくとも半分です。除数のリストは遅延生成されるため、

isPrime :: Integer -> Bool
isPrime p = (divisors p) == [1, p]

は O(p の最小の素因数) です。これは、最初の約数> 1が見つかるとすぐに、等値テストが決定されるためです。複合pの場合、最小の素因数は<= √pです。

複雑さ< 2√nの素数性チェックは最悪 O(√n) であり、複雑さのチェックは 1 つΘ(answer)なので、実行されるすべての素数テストを合わせた作業は O(n) です。

要約すると、必要な作業の合計は です。O(n)これは、各ステップのコストがO(n)最悪であるためです。

実際、このアルゴリズムで行われる総作業量はΘ(n)です。が素数の場合n、必要な限りの除数のリストの生成は O(1) で行われますが、素数のテストはΘ(n)です。nが複合である場合answer <= n/2、必要な限りの除数のリストを生成するのは ですΘ(n)。

算術演算を O(1) と見なさない場合、 のサイズの数値n、つまりO(log n)ビットの算術演算の複雑さを乗算する必要があります。これは、使用されるアルゴリズムに応じて、通常は係数をわずかに与えます。上下。log n_(log n)^2

于 2012-07-26T11:30:18.560 に答える