我在用归纳法显示给定函数时遇到问题
foo :: [Int] -> Int
foo [] = 0
foo (x:xs) = max (max x (foo xs)) (max (-x) (foo xs))
返回给定 Int
列表的最大绝对值,运行时间为 O(2^n)
。
我到目前为止:
t(0) = 1
和 t(n>1)= 2 * t(n-1) + 4
其中 t
显示 n
元素列表的 foo
和 max
调用的总和。
Base Case: n = 0 => t(0) = 1 <= c * 2^0, for c >= 1
Induction Hypothesis: t(n) <= c * 2^n
Induction Step: n -> n+1
=> t(n+1) <= c * 2^{n+1}
<=> 2 * t(n) + 4 <= c * 2^{n+1} | Induction Hypothesis
<=> 2 * c * 2^n + 4 <= c * 2^{n+1}
<=> c * 2^{n+1} + 4 <= c * 2^{n+1}
这显然是错误的,我不知道如何解决这个问题。
提前致谢!
最佳答案
让我们试着证明一个更紧的界限,比如
t(n) <= c*2^n - k (*)
对于一些常量 c
和 k
。
假设 (*) 由归纳假设成立,我们得到
t(n+1)
= { recursive definition }
2*t(n) + 4
<= { induction hypothesis }
2*(c*2^n - k) + 4
<= { math }
c*2^(n+1) - 2k + 4
<= { ???? }
c*2^(n+1) - k
现在,我们只需要选择k
,这样我们就可以真正证明最后一步是正确的,但这很容易。
请注意,我们还需要检查基本情况 t(0)
,并选择 c
。
剩下的就交给你了。
关于haskell - 通过归纳证明指数运行时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54242680/