haskell函数的时间复杂度

Question

考虑以下函数isPrime的代码。

f :: Integer -> Integer
f n = head (filter isPrime [0..n])

假设isPrime k在O(k)时间内计算一个布尔值，f n的时间复杂度是多少?

我的想法是滤波器是线性时间，并且我们已知isPrime也是线性时间，所以f n的时间复杂度应该是O(n)。

这是正确的吗?是否有一种简单的方法来观察代码的时间复杂度?

Answer 1

如果我们可以假设isPrime将为2返回True，那么它将花费常数时间。实际上，它将首先调用isPrime 0，然后是isPrime 1，最后是isPrime 2。所有这些函数调用都需要常量时间，因为isPrime k在O(k)中运行。

如果我们不假设isPrime将返回什么，那么isPrime是线性函数的事实意味着它将花费O(n²)时间。实际上，我们每次调用isPrime k，它在0 (k)中运行，因此这意味着它在0 (Σⁿ₀k)中运行，因此(n²)

。

这是正确的吗?是否有一种简单的方法来观察代码的时间复杂度?

由于Haskell的懒惰，分析时间复杂度变得更加复杂。特别是因为例如filter isPrime [0..n]的时间复杂度取决于使用列表的函数(这里是head)。head将在列表的第一项处停止。由于filter是惰性的，因此它不会确定其余的项。因此，对于惰性函数来说，函数的时间复杂度的概念可能不那么直接。