数学建模常用技巧

《数学建模常用技巧》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模---常用技巧常用技巧计算复杂性分析算法设计精确算法近似算法算法计算量估计、算法优劣比较比较算法的好坏，从不同的角度出发，有各种不同的标准。在这里，我们仅就算法的计算速度作一个十分粗略的比较。例1（整理问题）给定n个实数a1,a2,…,an，要求将它整理成由小到大排列（或由大到小排列）的顺序：b1,b2,…,bn，b1≤b2≤…≤bn。（算法1）取出a1,a2,…,an中的最小者，令其为b1。从a1,a2,…,an中去除b1，在余下的n—1个数中选出最小者，令其为b2，…，直至得到b1,b2,…,bn。容易看出，为了排出b1,b2,

2、…,bn，算进行了n(n-1)/2次比较。（算法2）步0b1←a1步1设已有b1,…,bk(1≤k

3、>b4，可再和b6比（若a8

4、og2M的实例。两者的差别究竟有多大呢？让我们来对比一下。假如计算机每秒可作100万次运算，则算法A一小时大约可解一个规模为n=60000的实例，而算法B在一小时内只能解一个规模的实例且n每增加1，算法B求解时所化的时间就将增加1倍。例如算法B求解一个n=50的实例将连续运算357年多。现设计算速度提高了100倍，这对计算机来讲已是一个相当大的改进。此时算法A可解问题的规模增大了10倍，而算法B可解问题的规模只增加了log2100<7。前者可解问题的规模成倍成倍地增加而后者则几乎没有什么改变，今天无法求解的问题将来也很少有希望解决。由于这一

5、原因，人们对算法作了如下的分类：（多项式算法）设A是求解某一问题D的一个算法，对D的一个规模为n的实例，用fA(D,n)表示用算法A求解这一实例所作的初等运算的次数。若存在一个多项式P(n)和一个正整数N，当n≥N时总有fA(D,n)≤P(n)（不论求解D的怎样的实例，只要其规模为n），则称算法A为求解问题D的一个多项式时间算法，简称多项式算法。（指数算法）设B是求解某一问题D的一个算法，fB(D,n)为用算法B求解D的一个规模为n的实例时所用的初等运算次数，若存在一个常数k>0，对任意正整数N，总可找到一个大于N的正整数n及D的一个规模为

6、n的实例，对这一实例有fB(D,n)=O(2^kn)，则称B为求解问题D的一个指数算法。多项式算法被称为是“好”的算法即所谓有效算法，而指数算法则一般被认为是“坏”算法，因为它只能求解规模极小的实例。下面的表1列出了在规模大约为n时各类算法的计算量，而表2则反映了当计算机速度提高10倍、100倍时，各类算法在1小时内可求解的问题的模型的增长情况，（前三个是多项式时间的，后两个是指数时间的）表1几个多项式和指数时间复杂性函数增长情况算法要求的计算量规模n的近似值101001000n101001000nlogn336649966n3103106

7、1092n10241.27×10301.05×10301n!3628800101584×102567表21小时内可解的问题实例的规模算法要求的计算量用现在计算机用快10倍计算机用快100倍计算机nN110N1100N1nlognN28.2N267N2n3N32.15N34.64N32nN4N4+3.32N4+6.64n!N5≤N5+2≤N5+3由上可知4n2与2n2都是O(n2)，nlogn+3n是O(nlogn)，我们在以后分析时间复杂性函数时也往往忽略常系数和增长速度较慢的项，因为前者可通过提高计算机速度来提高效率，而后者增长速度最快的

8、项才是决定效率的关键因素。下面介绍六个最初的NP难问题（1）（3—满足问题，简记3—SAT问题）每一个句子都是一个三项式的SAT问题，称为3—SAT问题。例如，就是3—SAT的一