最壞情況下的時間複雜

Question

我試圖找出下列函數的最壞情況時間複雜度：

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

我知道，這不是有效的，由於主叫分鐘兩次第二模式匹配。但是，你會如何發現這種功能的最壞情況？

Answer 1

正如你注意到的，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 

Answer 2

此函數的最壞的情況是當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 ^Ñ

而這儘可能地糟糕。