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

两件事情：

  1. 任何时候你看到一个列表推导（就像你在 中一样divisors），或者等效地，列表上的一些系列map和/或filter函数（就像你在 中一样main），将其复杂性视为 Θ(n)，就像你对待 a for-loop 在命令式语言中。

  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功能的方式重新定义所有内容......

希望这有助于为您提供解决这些问题的正确心态！

于 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函数循环遍历从1到的所有数字n，并对每个数字执行 O(1) 运算，因此计算完整输出为 O(n)。请注意，当我们说 O(n) 时，n 是输入数字，而不是输入的大小！由于存储 n 需要 m=log(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。所以，充其量，我们把工作减半——这对渐近成本没有影响。

于 2012-07-26T03:28:12.550 回答
2

Daniel Wagner 的回答很好地解释了为运行时复杂性推导界限的一般策略。然而，与一般策略的情况一样，它会产生过于保守的界限。

所以，只是为了它，让我们更详细地研究这个例子。

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

像 Daniel 一样，我假设算术运算、比较等是 O(1) - 虽然不正确，但对于所有远程合理的输入来说，这已经是一个足够好的近似值了。

因此，在列表中，必须生成candidates从n下到上的元素，元素的总成本为. 对于复合，我们有，那就是 Θ(n)。answern - answer + 1O(n - answer + 1)nanswer <= n/2

然后根据需要生成除数列表Θ(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)，并且对复杂性进行一次检查Θ(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 回答