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

Question

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

foo :: [Int] -> Int
foo    []  = 0
foo (x:xs) = max (max x (foo xs)) (max (-x) (foo xs))

returns 给定列表 Int 的最大绝对值，运行时间为 O(2^n).

我到目前为止：

t(0) = 1 和 t(n>1)= 2 * t(n-1) + 4 其中 t 显示 foo 和 max 对 n 元素列表的调用总和。

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。

剩下的就交给你了

Answer 2

让我们证明一个更普遍的说法。如果算法复杂度是这样的：

 t(0) = c
 t(n) = a*t(n-1) + b

假设 a>1 算法的复杂度为 O(a^n)。

我们选择k1 = c、d = b/(a-1)（这个d的选择到最后就会明了）、k2 = a + d。让我们假设 a > c（否则它会是 k1 = min(a,c)、d= b/(max(a,c)-1) 和 k2 = max(a,c) + d 但我懒得写所有这些 max 和 min).我们想证明

k1*a^n <= t(n) <= k2*a^n

但这里有一个转折，让我们证明更严格的上限：

k1*a^n <= t(n) <= k2*a^n - d

基本案例：

c <= c <= (a + d) - d

显然是真的

归纳步骤:

我们知道

k1*a^n <= t(n) <= k2*a^n - d

是真的，想证明

k1*a^(n+1) <= t(n+1) <= k2*a^(n+1) - d

左边很简单：

t(n+1) = a*t(n) + b >= a*t(n) >= a*(k1*a^n) = k1*a^(n+1)

右边有点复杂

t(n+1) = a*t(n) + b <= a*(k2*a^n - d) + b = a*k2*a^n - a*b/(a-1) + b = k2*a^(n+1) - b/(a-1) =  k2*a^(n+1) - d

最后一步是正确的，因为

a*b/(a-1) - b = b*(a/(a-1) - 1) = b*(a - (a-1))/(a-1) = b/(a-1)

换句话说

a*d - b = d

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

Proof exponential runtime by induction

math

big-o

haskell

runtime

induction