在递归函数分析递归调用数 [英] Number of recursive calls in Recursive function analysis

问题描述

读自行使用C中的罗伯特·Sedwick书算法++

Reading algorithms by self using Robert Sedwick book in C++

一个递归函数，把大小为N的问题分成两个   独立（非空）的部件，它解决了递归调用自身   比N倍以内。

A recursive function that divides a problem of size N into two independent (nonempty) parts that it solves recursively calls itself less than N times.

如果零件是一体的大小为k的大小和NK之一，则总   的，我们使用递归调用数目为T（N）= T（K）+ T（NK）+ 1，对于   N> = 1和T（1）= 0。

If the parts are one of size k and one of size N-k, then the total number of recursive calls that we use is T(n) = T(k) + T(n-k) + 1, for N>=1 with T(1) = 0.

将溶液T（N）= N-1是由直接感应。如果大小之和为   的值小于N时，证明呼叫的数量小于   N-1以下，从同一个归纳论证。

The solution T(N) = N-1 is immediate by induction. If the sizes sum to a value less than N, the proof that the number of calls is less than N-1 follows from same inductive argument.

我在上面的文字问题是

1. 如何笔者来到与解决方案，T（N）= N-1诱导？请帮我明白了。
2. 什么是笔者的如果尺寸总结为一个值小于N，则证明呼叫的数量小于N-1相同的归纳论证如下？
的意思

我是新来的数学归纳法所以有理解困难。

I am new to mathematical induction so having difficulty in understanding.

感谢您的时间和帮助

推荐答案

（1）通过归纳：

T(1) = 0 (base)
T(N) = T(k) + T(N-k) + 1 (definition of problem)

我们假设每个 N'LT; ñ，我们得到 T（N）= N-1
由于两个 K 和 NK 较小则 N ，我们从归纳假设得到：

We assume for each n < N, we get T(n) = n-1
Since both k and N-k are smaller then N, we get from the induction hypothesis:

T(N) = (k-1) + (N-k-1) + 1 = N-1
         ^        ^
        T(k)    T(N-k)

（2） 使用相同的参数： 如果

(2) Using the same argument: if

T(N) = T(k) + T(m) + 1 where k+m < N

那么同样证明会导致 T（N）＆LT; N-1

这篇关于在递归函数分析递归调用数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！