Algo and Matrix

《Algo and Matrix》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、AlgorithmandMatrix本短文讲述两件事。第一件是简介算法Algorithm一词的由来，面向广大的受众。第二部分需要一定的线性代数知识，将运用矩阵特征值等价地计算Fibonacci数列的通项。Algorithm,Algorism,andAlgebraAlgorithm一词是纪念九世纪的波斯穆斯林数学家花拉子米Al-Khwarizmi（全名AbuAbdullahMuhammadibnMusaAl-Khwarizmi阿布阿卜杜拉穆罕穆德伊本花拉子米）。花拉子米在一本书中总结了十进制数字系统中执行算术运算（甚至计算π的小数部分）的基本规则，叫做Algorism

2、。这些计算过程是如此的精确、无歧义、机械和高效，以至于到了十八世纪的欧洲，数学家们把花拉子米名字Al-Khwarizmi的拉丁文翻译Algorithm当作具有确定性过程的代名词。每当提到algorithm，他就是Al-Khwarizmi。花拉子米的书原名叫“Kitabal-jabrwaal-muqabalah”（大意为“RulesofReintegrationandReduction”），这本书为他赢得了代数学之父的美誉。其中代数Algebra就源于该书名中的”al-jabr”。题外话1：作为计算机数字基础的二进制代数系统，是由英国人GeorgeBoole发明的。C

3、++和Java等程序设计语言中的布尔类型bool（或者boolean）就是纪念这个人。题外话2：算法概念的形式化（计算模型）直到二十世纪三四十年代才由图灵（AlanTuring）的图灵机和丘奇（AlonzoChurch）的lambda演算完成，这也成为了计算机科学的基础。现在广为人知的”Church-TuringThesis”是由丘奇的学生StephenKleene在1943年首先定义的。Algorithm,Fibonacci,andMatrix事实上，如果没有LeonardoFibonacci先生，花拉子米的工作在欧洲也许就没有那么稳固的立足之地了。Fibonac

4、ci是十五世纪的意大利数学家，Leonardo更为人熟知的是以他名字命名的Fibonacci数列（以下简称F数列）：F0=0,F1=1,1,2,3,5,8,13,21,…,F30=1346269,…递归表达式如下：F(n)=F(n-1)+F(n-2),n>1F数列的增长有多快呢。让我们来算算，F31=1346269，就超过了一百万！实际上，F数列增长的几乎与2的幂次一样快：0.694nnF≈≈21.6n如何计算Fn呢。最简单的方法就是按照其数学定义即可：functionfib1(n):if(n==0)return0;if(n==1)return1;returnfib

5、1(n-1)+fib2(n-2);这是一个递归程序，时间复杂度是指数级别：T(n)=T(n-1)+T(n-2)+3>F(n)（其中T(n)表示当输入规模为n需要的时间，时间度量以一步基本操作计算，如3代表两步if语句判断操作加上一步加法操作）有没有更快的计算方法呢。注意到，上述递归算法有很多重复计算的步骤，比如计算F(5)是计算了一遍F(3)，而F(4)时又计算了一遍F(3)。一个更好的方法是存储已经计算好的F(i)，当需要用到它时直接读取即可。functionfib2(n):if(n==0)return0;if(n==1)return1;Allocateanarr

6、ayf[0…n]f[0]=0;f[1]=1;for(i=2…n){f[i]=f[i-1]+f[i-2];}returnf[n];上述算法用线性的空间将指数时间降到了多项式时间。如果将加法操作看作是一个基本操作（意味着单位时间内可以完成），则时间复杂度是线性的。但是考虑到F数列增长极快，而大整数的加法不是一个基本操作，而是线性的，因此上述算法更接近于二次复杂度。还有更好的算法吗。/***********************************************************************************************

7、************************/你可能依稀记得F数列有一个通项公式：nn115+−115F=−(E1)n5522直接带入公式计算不是更快吗！等等，别急。F数列是一个自然数的序列，而上述公式中竟然出现了无理数，太神奇了。对于有限精度的计算机来说，这不是一个好消息。这个时候，矩阵计算粉墨登场了！首先，将F数列以矩阵记号的形式重新表述，F1=F1，F2=F0+F1：F10,1F0=⋅F21,1F12FF200,1F10,1=⋅=⋅F31