haskell - 通过归纳证明指数运行时间

Question

我在用归纳法显示给定函数时遇到问题

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}

这显然是错误的，我不知道如何解决这个问题。

提前致谢!

Answer 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。

剩下的就交给你了。