Haskell函数f的时间复杂度分析及快速估算方法问询

先看给定的函数：

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

已知isPrime k的时间复杂度为O(k)，你的思路不正确，原因如下：
Haskell是惰性求值语言，filter结合head时，不会遍历整个[0..n]列表，只会逐个检查元素，直到找到第一个满足isPrime的元素就停止计算，直接返回该元素作为head的结果。

第一个满足isPrime的数是2（0和1都不是素数），只要n >= 2，函数只会依次检查0、1、2三个数：

• 检查0：isPrime 0的时间是O(0)
• 检查1：isPrime 1的时间是O(1)
• 检查2：isPrime 2的时间是O(2)

这三个操作的总时间是常数级，因此f n的时间复杂度是O(1)（当n≥2时）。如果n<2，函数会因head空列表报错，属于边界异常情况，不纳入常规时间复杂度分析。

快速估算Haskell代码时间复杂度的简便方法 #

• 优先考虑惰性求值特性：像filter、map这类函数，只要后续操作（如head、take k）不需要整个列表，就只会计算到所需的元素为止，不要默认按遍历全列表算复杂度。
• 定位终止条件：明确函数停止计算的节点——比如这里是找到第一个素数，而非遍历到n，终止节点的位置直接决定了计算量。
• 叠加子操作的实际开销：不要笼统地把“线性遍历”和“子操作线性复杂度”直接相乘，要结合实际执行的子操作数量和每个子操作的输入规模。比如这里子操作只执行了3次，且每次的k都是小常数，总开销自然是常数级。
• 区分最坏/平均/实际场景：如果题目是找列表中最后一个素数，那才需要遍历到n，总复杂度会是O(1+2+...+n)=O(n²)，但不同场景的终止逻辑差异极大，必须针对性分析。

内容的提问来源于stack exchange，提问作者Matt