分析Haskell函数的运行时效率

Question

我在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给出的分钟限制.那么如何分析代码的时间复杂度以确定我需要进行更改的位置？

注:请不要不张贴替代算法.我想自己解决这些问题.现在我只想分析我的代码并寻找改进它的方法.谢谢!

Answer 1

两件事情:

1. 每当你看到列表理解(如你所见divisors),或者相当于列表中的一些序列map和/或filter函数(如你所见main)时,将其复杂度视为Θ(n),就像处理一样for用命令语言循环

2. 这可能不是你期望的那种建议,但我希望它会更有帮助:Project Euler的部分目的是鼓励你思考各种数学概念的定义,以及许多不同的算法.可能正确地满足这些定义.

好吧,第二个建议有点过于模糊......我的意思是,例如,你实现的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 2

让我们从顶部开始吧.

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.所以,充其量,我们将工作减半 - 这对渐近成本没有影响.