F# 函数的最坏情况渐近时间复杂度

Question

我正在尝试找出以下函数的最坏情况渐近时间复杂度：

let rec min = function
| [k] -> k
| k::ks -> if k <= min ks then k else min ks

我知道它效率不高，因为在第二次模式匹配中调用了 min 两次。但是你如何找到这个函数的最坏情况？

Answer 1

此函数的最坏情况是 k 总是大于 min ks，如 [n, n-1, n-2 ... 1 ].

在这种情况下，对于数组的其余部分，您将在每次迭代中运行 min 两次，这等于：

T(n) = 2T(n - 1)
T(n - 1) = 2T(n - 2)
T(n - 2) = 2T(n - 3)
...
T(1) = 1

回到T(n)，我们可以看到：

T(n) = 2*2*T(n - 2)
= 2*2*2*T(n - 3)
= 2ⁿ

这已经很糟糕了。

Answer 2

如您所见，min 函数是

calling min twice in the 2nd pattern match

在最坏的情况下（最小值在列表末尾），它对列表的每个元素调用 2 次，每个元素再次调用自身两次以获取列表的尾部，...

所以复杂度是O(2^n)。

如果对 min ks 进行一次计算并使用该值，则复杂度将为 O(n)。

let rec min = function
    | [k] -> k
    | k::ks -> 
        let minTail = min ks
        if k <= minTail then k else minTail

worst-case asymptotic time complexity of F# function