|
|
这个计算机科学讲义的Prop 6.1.3(第8页)$\newcommand{\S}{§}$
Prop 6.1.3. Given two numbers $n$ and $m$, with $n \geq m$, let $f_{r}$ be the smallest Fibonacci number that exceeds $n$. Then the number of recursive calls in the Euclidean algorithm is at most $r$.
Proof: Suppose that there are $s$ calls. Then let
$$
n_{0}, n_{1}, \ldots, n_{s}
$$
be the sequence of values of the first argument in the successive calls. Thus,
$$
n_{0}=n \quad \text { and } \quad n_{s}=\operatorname{gcd}(n, m)
$$We observe that $n_{s} \geq 1>f_{0}$ and that $n_{s-1} \geq 2>f_{1}$. It follows by induction, in general, that
$$
n_{s-k-2}>f_{k+2}=f_{k+1}+f_{k}
$$
because
$$
n_{s-k-2} \geq n_{s-k-1}+n_{s-k}>f_{k+1}+f_{k}
$$
In particular, $n_{0}>f_{s}$. Therefore, $s<r$.
Remark: Intuitively, the number of recursive calls is at its largest, relative to the size of the numbers supplied as input, when the input supplied is two consecutive Fibonacci numbers, since then all the quotients are 1 , each remainder is the next lower Fibonacci number, and the numbers passed in the recursion are reduced as little as possible at each step. Since the growth of the Fibonacci sequence is exponential, as we proved in $\S 2.5$, we conclude that in this computationally "worst case", the number of recursive calls is proportional to the logarithm of the size of the input. |
|
abababa
Posted 2017-10-31 08:33
hbghlyj
Posted 2019-9-22 00:29
