分析Haskell的功能

Question

我已經在Haskell以下解決Problem 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 

但是，它需要的時間比項目歐拉給出分鐘的限制更多。那麼，如何分析我的代碼的時間複雜度以確定需要進行更改的位置？

注意：請做不是後替代算法。我想自己弄清楚這些。現在我只想分析我的代碼並尋找改進它的方法。謝謝！

Answer 1

讓我們從頭開始。

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

現在，讓我們假設某些東西都是便宜的：遞增的數字是O（1），做mod操作是O（1），並與0比較是O（1）。 （這些都是錯誤的假設，但是什麼）divisors函數遍歷從1到n的所有數字，並對每個數字執行O（1）操作，因此計算完整輸出爲O（n）。注意在這裏當我們說O（n）時，n是的輸入數字，而不是的大小的輸入！由於需要m = log（n）位來存儲n，所以該函數在輸入大小中花費O（2^m）時間來產生完整的答案。我會一直使用n和m來表示下面的輸入數字和輸入大小。

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）

現在，有一個最後的細節需要考慮：在上面的分析中，我始終假設每個函數/子表達式都被迫產生其整個輸出。正如我們在main中看到的那樣，這可能不是真的：我們稱之爲head，這隻會強制列表的一小部分。但是，如果輸入數字本身不是素數，我們肯定知道我們必須查看至少一半的列表：在n/2和n之間肯定不會有除數。所以，我們最好把工作減半 - 這對漸近成本沒有任何影響。

Answer 2

兩件事情：

1. 你看到一個列表理解（如你在divisors）任何時間，或者等價地，一些系列map和/或filter功能在列表（如你在main ），將它的複雜度視爲Θ（n），就像您在命令式語言中使用for -loop一樣。

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函數的方式...

希望這有助於爲您解決這些問題提供正確的思維方式！

Answer 3

Daniel Wagner's answer解釋了爲運行時複雜性推導界限的一般策略。但是，通常情況下，一般策略的情況下，它會產生過於保守的界限。

因此，我們來仔細研究一下這個例子。

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）假設工作 - 作爲n不錯，對於所有遠程合理的輸入來說，這是一個足夠好的近似值。

因此，列表candidates，都將產生從n元件向下answer，n - answer + 1元件，對於一個O(n - answer + 1)總成本。對於複合n，我們有answer <= n/2，那麼這就是Θ（n）。

根據需要生成除數列表然後Θ(n - answer + 1)也是。

對於n的因數d(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）的複雜性的素數檢查，以及一個複雜的檢查Θ(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的因子。