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

Question

我试图弄清楚以下函数的最坏情况渐近时间复杂度:

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

我知道它效率不高,因为在第二次模式匹配中调用min两次.但是你怎么能找到这个功能更糟糕的情况呢？

Answer 1

正如您所注意到的,min功能是

在第二次模式匹配中调用min两次

在最坏的情况下(列表末尾的最小值),对列表的每个元素进行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