考慮下面的函式 isPrime 的代碼。
f :: Integer -> Integer
f n = head (filter isPrime [0..n])
假設在O(k)isPrime k時間內計算一個布林值，那么 的時間復雜度是多少？f n
我的想法是 filter 是線性時間，給定isPrime的也是線性時間，所以時間復雜度f n應該是O(n)。
這是正確的嗎？是否有一種簡單的方法來觀察代碼的時間復雜度？
uj5u.com熱心網友回復：
如果我們可以假設isPrime它將回傳True，2那么它需要恒定的時間。實際上，它會先呼叫isPrime 0，然后呼叫 ，isPrime 1最后呼叫isPrime 2。所有這些函式呼叫都需要恒定的時間，因為isPrime k在O(k)中運行。
如果我們不假設isPrime將回傳什么，那么isPrime作為線性函式的事實意味著它將花費 O(n 2 ) 時間。事實上，我們每次呼叫isPrime k，它在O(k)中運行，這意味著它在O(Σ n 0 k)中運行，因此在(n 2 )中運行。
這是正確的嗎？是否有一種簡單的方法來觀察代碼的時間復雜度？
由于 Haskell 的懶惰，分析時間復雜度更加復雜。特別是因為例如時間復雜度filter isPrime [0..n]取決于使用該串列的函式（此處head）。head將停在串列的第一項。由于filter是惰性的，因此它不會確定其余的專案。因此，惰性函式的函式時間復雜度的概念可能不太直接。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/531105.html
標籤：哈斯克尔时间复杂度
上一篇：將不同型別轉換為字串