一起来算圆周率 | 日志 | 果壳网 科技有意思
自古计算圆周率是数学界一项流行运动，各大数学家争相破记录以名垂青史。想象有人为圆周率，算的不是圆周率而是寂寞啊！自有圆周率，计算比的是数学；后有现代数学，计算比的是寂寞；自从有了计算机，计算变成程序员们（另一种）练手的健康活动：锻炼编程技术之余可比肩历史伟人，看官也来一发吧！不懂数学没关系，计算圆周率并不需要多少数学知识，你需要的只是一些编程基础、一点数据结构知识，还有本文准备给你的：算法。（题外话：如果本文中所有公式都显示成叉，说明你在使用古董级浏览器，请升级……）========【摘要】========1）本文介绍编程计算圆周率的主流算法，从简单到复杂任君选择，目的是让读者看完能动手算一把。2）不涉及具体的编程语言技术，也不涉及数学证明。3）所有算法都不限编程语言，你可以用你最擅长的语言来实现。不过在科学计算领域，C/C++兼顾性能和便捷，依然是首选，文中少量示例都用C/C++。4）即使你没时间动手，本文也可带你浏览一下科学计算王国。【读懂本文，你需要一点点的……】1）编程基础2）数据结构基础3）高等数学基础========【概述】========千言万语不如先来一发：#include &stdio.h&int main(){ double p = 3; for (int i = 2 ; i &= 100000 ; i+=4) { p += 4 / (double(i)*(i+1)*(i+2)); p -= 4 / (double(i+2)*(i+3)*(i+4)); } printf("pi=%.14f\n", p); return 0;}请把以上代码拷进C语言开发环境里运行，瞬间出结果如下：pi=3.79恭喜！14位小数无一错误！你已经破了公元1400年的纪录！祖冲之那7位小数真的弱爆啦！……只是开了个玩笑，算圆周率前请先拜大神，可保佑不溢出：祖冲之（ 公元429年4月20日─公元500年），我国杰出的数学家，科学家。曾计算出圆周率7位小数，是之后近1000年的世界纪录保持者。凡是讨论算法，必谈时间复杂度。祖冲之的年代，圆周率源自几何也算以几何，原理是在圆周割成多边形来计算周长，称为几何算法，时间复杂度高、计算量极大。经过现代数学和计算科学的发展，圆周率计算方法变得非常高效，例如上面的C语言例子用的是以下无穷三次级数：不用计算机，笔算也能算出好几位，时间复杂度是O(10^(N/3*2))（N是十进制位数，下同），但仍不足以计算成千上万位。另外，例子中用double（双精度浮点数）类型来计算圆周率，但编程语言支持的浮点类型最多就十几、二十位几小数，显然上面那种简单的程序无法算出更精确的pi。为了让计算机处理超长的小数，我们要用很大的数组来储存小数（称为【高精度计算】），并为此实现专门的加减乘除、开方算法。本文后续将详细介绍高性能的圆周率计算方法和与之配套的高性能高精度计算。圆周率计算方法极多，但不是每种都能高效实用。现代圆周率计算方法主要有两种：基于无穷幂级数（简单，O(N^2)）基于超长小数运算（高速，O(N logN)）第一种方法基于pi可以分解成一组幂级数和，例如等一下我会介绍的贝利－波尔温－普劳夫公式：非常简单有效的算法，用最基本的高精度四则运算即可实现，没有高精度的分母，没有两个大数相乘，更没有开方，时间复杂度是O(N^2) ，推荐从这个上手。第二种方法包括稍后介绍的高斯-勒让德算法，依靠上世纪60年代发明的神器快速傅里叶变换而达到时间复杂度O(N(logN)^2)，位数多时优势明显，是世界纪录和众多圆周率计算软件的算法，包括著名的SuperPI，但用到的高精度计算技术稍复杂。========【高精度计算基础】========在圆周率计算和各种科学计算中，都用数组来储存一个很长的小数（或者超大的整数，或小数点前后都有很多位）。例如，下面表示用【高精度数组】a储存的圆周率，数组每个单元保存8位十进制小数：等同于：其中是进制。一般地，小数A用高精度数组a基于d进制储存可表示为：计算机的储存空间有限，所以n是一个有限的整数。进制d一般是10或者16的整数次幂，其中16整数次幂的方法对储存的利用率更高、进位计算更快速，但输出时转成十进制需要很大的计算量（O(N^2)），有时甚至比计算pi本身更耗时间。对高精度数组表示的小数进行各种加减乘除运算，称为【高精度计算】。例如，最简单的高精度计算是加法，把两个高精度数组对位相加，即可得出两个小数的和高精度小数：代码看起来是这个样子的：for (k=0 ; k& k++)c[k]=a[k]+b[k];如果结果中若干项超过进制d，则对其进行进位运算。C语言进位的代码看起来是这个样子的：for (k=n-1 ; k&=0 ; k--)if (a[k] & d){a[k-1]=a[k]/d;a[k]=a[k]%d;}进位可能也造成a[k-1]也超过了d，于是进位从最低位a[n]一直到最高位a[0]反向遍历执行。减法（或者负数加法）的原理也类似，对位相减后执行退位操作（略）。【高精度乘法】基本计算方法是【卷积】，小学时教我们的竖式乘法本质也是卷积。所谓卷积，就是多项式每一项都与另一个多项式的每一项相乘、累加：小学教的竖式乘法就是卷积，被乘数和乘数各位两两相乘、相加、进位：高精度数组a和b相乘的数学表达是：所以C的每一项是：上面的式子看傻了没关系，高等数学就是喜欢把简单的东西写得很复杂……其实原理极简单，代码看起来是这个样子的：for (k=0;k&n;k++)for (j=0;j&m;j++)c[k+j]+=a[k]*b[j];同样要进行进位操作。两个n位精度的小数相乘，虽然结果有2n-1项，但其实精度只有前面n项是准确的，后n-1项丢弃或不予计算。卷积的时间复杂度是O(nm)。如果加减乘对你来说都没有压力，那【高精度除法】也许能给你带来一些麻烦。高精度除法基本算法就是小学教的竖式除法：试除一位x、计算【被除数-（x×除数）】得余数，余数进行退位运算后作为被除数重复上面的过程。如果除数是一个整数，这个并不会很困难，试除用的是被除数的前几位除以除数。但如果除数也是高精度数组就有点麻烦了，除数也要用前几位作为试除位来试除。这种基本除法算法时间复杂度是O(nm)，n是结果精度，m是除数精度，与被除数精度无关。实际上这种代码实现起来比后面的高性能计算方法更长更麻烦（因为后面介绍的方法把除法转化成乘法，可直接调用乘法的代码），所以这里略去。========【高精度数制的选择】========在你实现高精度运算时，需要决定数制，或写出兼容任何数制的代码（但这并不好）。所谓数制，就是我们平时使用的十进制、十六进制。唯一不同的，高精度的数制不是其显示出来的数制，而是其每个单元储存数据的上限。例如规定高精度10000进制，表示一个单元达到或超过10000时，应该减去10000，并对其高一位的单元加1（进位），或是一个单元小于0，则加上10000，其高一位减1（退位）。一般我们选用10或16的整数次幂作为高精度的数制，两者各有优缺点。10整数次幂的数制运算完后无需转数制可直接输出十进制的结果；而16整数次幂进制进位速度高，只需要用编程语言的位运算符，性能远好于取模、除法运算，而且下面的BBP公式和十六进制是绝配，通用所有数制的程序几乎不可能利用有这些优点，我们没必要写出通用的程序。因此，有时我们可能选择用16整数次幂进制计算，然后转成十进制输出。转换算法很简单，对于任意一个高精度16整数次幂进制的小数，重复下面的步骤：整数部分直接用十进制输出丢弃整数部分整个高精度数组乘以10^n，并用原来的数制执行进位回到1重复这个过程，直到输出十进制位数达到十六进制位数的1.2倍（）以上计算每一个循环能输出n位，总时间复杂度是O(N^2)：这个是个大问题，超过了高斯-勒让德算法的时间复杂度，所以如果用16整数次幂进制跑高斯-勒让德算法然后再转十进制会得不偿失，转换的速度甚至比计算更慢。幸好，这个计算易于实现多线程并行运算，很容易充分发挥CPU超过4个线程的性能。现在你已经学会了基本的高精度计算，用BBP来算已经难不倒你了。========【贝利－波尔温－普劳夫公式（BBP公式）】========BBP公式是圆周率计算的众多无穷幂级数方法之一，均具有O(N^2)的时间复杂度，优点是实现简单、极容易实现多线程并行运算、内存使用效率高，使用最为广泛。其计算过程是这样的：其中每个方块都表示一个高精度数。留意左边1/16^k越来越少，总有某一项之后小于你设置的高精度数组的精度，之后就不用计算了，可输出结果。计算过程只有高精度加法、减法，高精度数乘除非高精度整数。计算总项数n正比于计算精度，每轮计算涉及的高精度计算时间复杂度都是O(N)，所以总复杂度是O(N^2) 。刚才说，BBP和十六进制是绝配，不只是因为免去左边除以16的O(N)除法，还因为BBP公式在十六进制计算时可以只计算其中某些位而无需计算前面的未，例如从n位计算到n+m位，时间复杂度是O(n*m)。基于这个特点，BBP不是圆周率幂函数计算公式最高效的一个，却最适合多线程并行和分布式计算，还能用来验算其它算法算出来的十六进制结果。考虑到一点跑题，不在这里详述，有兴趣可看看（较简单）。========【高斯-勒让德算法（GLA）】========BBP之类的O(N^2)方法很简单，但在世界纪录级别（万亿位）难等大雅之堂，我们需要的一些O(N logN)级别的神器。其中最简单的是GLA，SuperPi用的就是这个。GLA写出来很简单。初始化：迭代：最后计算pi为：其中，除了p外，其余（a，b，t，pi）都为高精度数，例如计算100万位圆周率，则这4个高精度数都是100万位。迭代过程中，a和b会不断接近，迭代结束条件是a和b的差距超过其本身精度的一半（例如计算100万位，那结果a和b第一个不同的位在50万位后即可结束迭代）。p是普通的整型。每迭代一次，a和b的差的数量级增加一倍，所以迭代次数为O(log N)，计算100万位的圆周率约需要迭代20次。GLA难点和主要计算量在高精度乘法和开方，乘法和开方的性能决定GLA的性能。要使GLA的时间复杂度达到O(N (log N)^2)，你需要下面的算法。========【高精度乘法-快速傅里叶变换】========基本的高精度乘法用卷积，时间复杂度O(nm)，用它的话我们GLA的O(N (log N)^2)就报销了。我们要祭出神器中的神器：FFT——快速傅里叶变换。有了FFT，对大数乘法、除法、开方通通有了过往不可想象超高性能，Pi的位数疯狂增长。尽管我尽了最大努力，但本节仍是这篇文章最难读懂的部分，你可能会一头雾水——没办法，神器自有神器的架子，在我自行参透前网上几乎没找到清晰的讲解，所以写这部分结合了我自己的经验，着重解释最难理解的部分，并使用大量的图示，尽可能让过程更直观。尽管看起来很复杂，但代码核心部分也只有10-15行，因为其有着惊为天人的对称性，体现着让人叹为观止的数学美。【傅里叶变换】和【快速傅里叶变换】：【傅里叶变换】本来不是用来算乘法的，而是用来分解波（例如声音或者电磁波），而用来做卷积则是上世纪自有计算机后发现的。傅里叶变换将一组复数通过一系列计算转换成另外一组复数，转换前后复数个数一样，转换后的每个复数都和转换前每个复数相关。【快速傅里叶变换】泛指可以在O(N logN)时间复杂度内完成傅里叶变换的算法。根据卷积定理，两个多项式的卷积的傅里叶变换等于其各自的傅里叶变换对位相乘，如果结合快速傅立叶变换，就可以在O(N logN)的时间复杂度内完成高精度乘法。本文只介绍算法而不论数学原理和证明，其实我还没搞懂我会告诉你吗？【算法总体流程】假设要对高精度数组A和高精度数组B以快速傅里叶变换计算卷积，总体流程如下：把数组A转换成复数数组A'；对A'执行快速傅里叶变换，得复数数组A''；同上方法，把高精度数组B转换成B'，执行快速傅立叶变换得B''；A''和B''对应单元相乘，得复数数组C''；对C''执行快速反傅里叶变换，得复数数组C'；C'重新转换成高精度数组C，即为计算结果。如图：其中，转换就是普通的数据类型转换，整数转成一个虚部为0的复数，或者复数舍弃虚部，实部四舍五入成整数。“快速反傅里叶变换”（IFFT）是“快速傅里叶变换”（FFT）的逆过程。事实上由于数学上的对称性，两者几乎是一样的，核心代码只用一套，无需分别写。快速傅里叶变换有多种具体算法，以下介绍最简单的“库利－图基快速傅里叶变换”【C-T FFT】。【转换】C-T FFT要求上图中所有复数数组统一大小，且为2的整数次幂，不小于相乘两个数的长度和，所以计算前需要先补0。假设计算1.11×2.22，高精度数组是十进制，1.11和2.22都是3个单元的精度，3+3=6，不小于6的2的整数次幂是8，所以整个流程看起来是这样的（用(a,b)表示复数a+bi，下同）：【转换精度问题】复数使用两个浮点数表示，计算机支持的64bit浮点数一般只有54bit的有效位数（GCC支持96bit long double类型并不通用）。假设高精度整数数组每个单元是 x bit，即不大于进制，FFT长度是，那么为了防止精度不足而造成计算错误，x和N必须满足：这个条件相当苛刻，意味着 x 得不超过16，即不超过2^16=65536进制。如果用10整数次幂计算，不能超过10000进制。所以当你用的数制较大，转复数数组时必须拆开到65536进制或10000进制。当高精度数组尺寸达到约2^24时，还得进一步下降到256进制和100进制。【结果精度问题】用n位d进制表示一个无穷小数时，误差不超过，那么两个小数相乘后，结果误差不超过（和加减法一样），仍然是n位，超过n位即使算出来也是不准确的，可以舍去。证明很简单，略。【FFT 和 IFFT】刚才提到，傅里叶变换和反傅里叶变换有漂亮的对称性，IFFT只需在FFT前后再加一点东西：其中，共轭就是复数数组中所有单元的虚部取负值（高中数学呀），归一化就是全部复数除以N（数组的大小）。由于我们计算高精度乘法时，输出结果虚部一定是0，所以最后一个共轭计算可以节省。【FFT过程】公式神马的最讨厌了，要说清楚FFT，千言万语不如一张图：即使你没看明白也一定能感受到这图的震撼，它有着各种完美的周期性和对称性。留意从顶上的输入数组到底下输出结果数组有很多连线，输入的任意单元和输出的任意单元之间有且只有一条通途。其中W(k,N)是“旋转因子”，表示模为1，-k/N个圆周角的复数，即：(*)所谓位元反转排序就是把数组单元的序数k的N位二进制全部位取反，例如：4的二进制是100，把所有位反过来是001，是1的二进制，所以x4和x1交换。N=8时，0、5等因为位元反转后仍是自身，所以x0、x2、x5、x7无需换位。请细细观察图中的规律，直到你有点头绪了，看看下面我归纳的规律：一、对于N=2^p的FFT，有p轮计算。二、每一轮计算都两两组合。三、决定如何组合两个单元的规律在于两个单元的序数的二进制，例如第二轮组合的是：十进制：0-2、二进制：000-010十进制：1-3、二进制：001-011十进制：4-6、二进制：100-110十进制：5-7、二进制：101-111观察组合的左右两个序数只有中间一位不同，推广到N=2^p都有相同的规律，第 x 轮组合的是右数第 x 位不同的两单元，第 x 位称为第 x 轮的【异位】。四、组合右边的单元乘以W(k,N)，留意到 k 的规律，和组合的两个数密切相关，是两数【异位】右边部分的左移b位，第1轮b=2，第2轮b=1，第3轮b=0。举例：第二轮，对于组合1-3（二进制：001-011）异位是右数第二位，异位右边是二进制1对1左移b=1位，得10，十进制2所以第二轮1-3组合的W(k,N)中，k是2五、组合的两个单元执行交叉加减法，左'=左+右，右'=左-右算法都在上面了，你可以动手写程序了。你需要看清楚图中每一轮转换的规律，写出适应任意N=2^p的计算代码。【优化】基于大数运算来计算圆周率的算法大部分时间都用来FFT，所以提高FFT性能是关键。下面是一些优化思路，需要一定的编程功底，可根据你自己的能力选择使用哪些。【优化1：旋转因子缓存】计算中重复使用旋转因子，计算机计算cos和sin的速度较慢，可将其一次计算并保存在数组中，计算时直接提取，在整个计算过程中会被重复调用，可有效节约计算时间。【优化2：CPU指令集优化】FFT中涉及大量复数运算，SSE系列指令集非常适合对其进行优化。VC和GCC编译器都有提供库（但不统一）来直接调用SSE指令集，经在VC中测试，对32位编译的程序性能提升达3倍，而64位编译程序提升没那么多但仍然显著，可能64位编译时已经有一些智能的方法自动调用SSE。【优化3：多线程优化】FFT算法是典型的分治算法，非常适合多线程并行运算。注意上面的计算流程图，除了第三轮计算，前面的计算是左右独立的，意味着前两轮可以建立2个线程分别计算左右部分，两者汇合（Join）计算最后一轮。同理，第一轮可以分成4个线程计算，计算完毕后两两汇合成两组计算。当N非常大，可以很容易将计算量分摊到所有CPU线程中，例如N=，为10轮计算，CPU有4个线程，则前8轮分成4个线程计算，第9轮汇合成2个线程计算，最后第10轮一个线程完成计算。========【高精度除法/开根号：牛顿迭代法】========费了九牛二虎之力搞掂了FFT，我们的高速算pi已经几近成功了，接下来我们用牛顿迭代法把除法和开方转成乘法，那就功德完满了。我们先来复习一下牛顿迭代法：牛顿迭代法可以用来计算任意2阶可导的函数f(x)=0的数值解。假设方程在附近有一个解，那么使用迭代公式：那么x序列将越来越接近方程的解，每迭代一次有效小数增加一倍。对于除法和开方，f(x)有不只一种，要找到适当的f(x)，使迭代过程中没有除法和开方，只有乘法。【除法算法】计算a/b，先用牛顿迭代计算1/b，f(x)是：迭代式：【取倒数算法】迭代结果再乘以a，即为a/b。由于牛顿跌代法对任意一步的误差都不敏感，你可以取任意初始值来计算，不过最好的方法是将b的前几个单元换算成浮点数，计算1/b然后开始迭代。由于开始迭代时精度低，无需用太高精度的数组，b也截断到较低精度，然后每迭代一次的精度增加一倍，直到达到指定的精度。如此，每迭代一次的开销增加一倍，总计算量的一半在进行最后一轮的迭代。最后一轮迭代有2次乘法，再加上最后计算一个乘法，总计算量约是同样精度乘法的5倍，时间复杂度依然是O(N logN)。【开方算法1】计算a的开方：迭代（这个方法不好，看下面的【开方算法2】）： 虽然我们已经能算除法了，但这就成了迭代中的迭代，让人不舒服。【开方算法2】先计算：迭代 x 的f(x)是：迭代式：迭代完成后再用上面【取倒数算法】计算1/x即为计算方法与除法很相似，你甚至可以重用大部分代码。一次迭代3次乘法，开始时只需要截断到低精度计算并逐次精度加倍，总迭代计算量是6个乘法，加上取倒数是4个乘法，总共是10个乘法的计算量，时间复杂度依然是O(N logN)。测试证明【开方2】比【开方1】快20%左右，而且避免了迭代套迭代，推荐使用。========【写在最后】========本文主要介绍了这几个计算圆周率相关的要点：高精度计算BBPGLAFFT高精度乘法牛顿迭代高精度除法和开方事实上如果你掌握了高性能高精度计算方法，可以挑战一些更有难度但更快的算法。目前世界纪录是用巨型机跑出来的10万亿位，如果用SuperPI和普通CPU计算的话，它要吃掉600T的内存和耗时20年。笔者使用OpenCL编程开发的程序可使用GPU进行计算，可在3秒内完成一百万位计算，参见：
本文由授权（）发表，文章著作权为原作者所有。
觉得c语言那是想法，原理还是依靠千年前大神的想法！
引用 的话：觉得c语言那是想法，原理还是依靠千年前大神的想法！C语言那条程序的方法可是分析数学时代才有的算法，祖冲之那个年代可没有那么高效的的方法。
看晕了……
引用 的话：看晕了……如果哪里看不懂请提些意见，我可以改得更通俗些。不过话说还是需要一些高等数学和编程基础的，例如复数乘法不懂话，的确不可能学会FFT。
正在学C和高等代数的大一党表示喜闻乐见
引用 的话：如果哪里看不懂请提些意见，我可以改得更通俗些。不过话说还是需要一些高等数学和编程基础的，例如复数乘法不懂话，的确不可能学会FFT。还只是个高中生，刚学完复数……没有多少高数基础倒是有点编程基础……我还是有时间再仔细看看吧，感觉写的还是很不错的
引用 的话：还只是个高中生，刚学完复数……没有多少高数基础倒是有点编程基础……我还是有时间再仔细看看吧，感觉写的还是很不错的不错，加油
引用 的话：还只是个高中生，刚学完复数……没有多少高数基础倒是有点编程基础……我还是有时间再仔细看看吧，感觉写的还是很不错的需要高数基础的部分主要是牛顿迭代法那部分，当然其实不用看懂直接套我给的公式也就可以了。不过我估计动手写起来，数学功底还是很重要的。
引用 的话：需要高数基础的部分主要是牛顿迭代法那部分，当然其实不用看懂直接套我给的公式也就可以了。不过我估计动手写起来，数学功底还是很重要的。我还是有时间稍微学一下牛顿迭代法吧
不能更赞！！
引用 的话：不能更赞！！那么长！
这个条件相当苛刻，意味着 x 得不超过16。 我有疑问：p=3时，x应不得超过25.
引用 的话：这个条件相当苛刻，意味着 x 得不超过16。 我有疑问：p=3时，x应不得超过25.如果p=3，那也没必要用这么复杂的算法。其实这个限制可以通过“正负均衡进位制”来突破。（网上没找到这种算法叫什么，这个名字是我自己取的），我的另外一篇日志有介绍：
(C)2014果壳网&京ICP备号-2&京公网安备2179人阅读
2.1 插入排序
插入排序解决的问题：
&& &输入：n个数构成的序列&a1, a2, ..., an&
&& &输出：排序输入序列&a1, a2, ..., an&为&a1', a2', ..., an'&，满足a1' ≤ a2' ≤ ... ≤ an'
INSERTION-SORT(A)
for j &- 2 to length[A]
do key &- A[j]
i &- j - 1
while i & 0 and A[i] & key
do A[i+1] &- A[i]
i &- i - 1
A[i+1] = key
C代码：(C的数组下标从0开始，而伪码中从1开始)
void insertion_sort(int *arr, size_t size)
&& &int i, j,
&& &assert(NULL != arr);
&& &for (j = 1; j & ++j) {
&& &&& &key = arr[j];
&& &&& &for (i = j - 1; i &= 0 && arr[i] & --i)
&& &&& &&& &arr[i+1] = arr[i];
&& &&& &arr[i+1] =
正确性分析：
&& &说明：
&& &&& &插入算法在执行循环之前，A[1,j-1]是已排好序的，而每次循环都保持这个情况，因此当j从2到length[A]循环完成后，整个数组已排序。
&& &初始：
&& &&& &j＝2，A[1,j-1]只包含一个元素A[1]，因此是已排序的；
&& &保持：
&& &&& &对于任意j(2 ≤ j ≤ length[A])，保存A[j]到key
&& &&& &内部循环总是从A[j-1], A[j-2], ..., A[1]序列中依次查找所有大于A[j]的值并依次后移。
&& &&& &当循环结束时，A[i+1,j]中存放所有大于key的值，而A[1,i-1]中存放所有不大于key的值，且A[i]是空闲的。
&& &&& &存放key到A[i]。
&& &&& &因此每次循环后，A[1,j]是有序的。
&& &退出：
&& &&& &j & length[A]时循环结束，此时A[1,length[A]]全部有序。
数学归纳法证明：
&& &当j=2时，A[1,j-1]只包含一个元素A[1]，因此肯定是有序的。
&& &假定对于任意j=m(2 ≤ m & length[A])，循环完成后有A[1,j]有序
&& &则当j=m+1时：
&& &&& &A[1,m]肯定有序。
&& &&& &保存A[m+1]到key。
&& &&& &内层循环结束时，A[1,i]子数组中所有元素不大于key，而A[i+2,m+1]子数组中所有元素大于key，A[i+1]不持有有效数据。
&& &&& &保存key到A[i+1]。
&& &&& &综上可知：A[1,m+1]此时是有序的。
&& &因此对于所有的j(2 ≤ j ≤ length[A])，在任意时刻，有A[1,j]有序。
&& &当循环迭代到j=length[A]算法结束时，数组A已排序。
测试程序：
&& &可以通过如下程序测试插入排序算法的正确性。其中辅助函数print_arr、init_arr可能在以后多次用到：
#include &assert.h&
#include &stdio.h&
#include &stdlib.h&
#include &time.h&
void insertion_sort(int *arr, size_t size)
assert(NULL != arr);
for (j = 1; j & ++j) {
key = arr[j];
for (i = j - 1; i &= 0 && arr[i] & --i)
arr[i+1] = arr[i];
arr[i+1] =
void print_arr(const int *arr, size_t size, const char *info)
assert(NULL != arr);
printf(&%s: &, info);
for (i = 0; i & ++i)
printf(&%d &, arr[i]);
printf(&\n&);
void init_arr(int *arr, size_t size)
assert(NULL != arr);
srand((unsigned int)time(NULL));
for (i = 0; i & ++i)
arr[i] = rand()%100;
int main()
int arr[10];
init_arr(arr, 10);
print_arr(arr, 10, &before&);
insertion_sort(arr, 10);
print_arr(arr, 10, &after&);
2.1-1 以图2-2为模型，说明INSERTION-SORT在数组A=&31,41,59,26,41,58&上的执行过程。
41(j), 59,
31(j), 41,
59(j), 26,
59(j), 41,
59(j)标注为x(j)的元素表示此时正在以j执行循环。
2.1-2 重写过程INSERTION-SORT，使之按非升序（而不是按非降序）排序。
只需要更改一行：
&& &while i & 0 and A[i] & key
&& &while i & 0 and A[i] & key
2.1-3 考虑下面的查找问题：
&&& 输入：一列数A=&a1,a2,…,an&和一个值V。
&&& 输出：下标i，使得V=A[i]，或者当V不再A中出现时为NIL。
写出针对这个问题的线性查找的伪代码，它顺序地扫描整个序列以查找V。利用循环不变式证明算法的正确性。确保所给出的循环不变式满足三个必要的性质。
FIND-LINEAR(A, v, i)
&& &i &- NIL
&& &j &- 1
&& &while j ≤ length[A] and A[j] != v
&& &&& &do j &- j + 1
&& &if j ≤ length[A]
&& &&& &then i &- NIL
int find_linear(const int *arr, size_t size, int v)
for (i = 0; i & size && arr[i] != ++i);
if (i == size) i = -1;
/* -1 means NIL */
return (int)i;
&& &初始：
&& &&& &i＝NIL，初始化为未查找到。
&& &保持：
&& &&& &从j=1到length[A]，依次判断，如果A[j]等于v，则结束循环。
&& &退出：
&& &&& &循环结束时，判断j是否有效
&& &&& &如果j在有效范围（小于等于length[A])，则证明查找成功，因此设置i为正确的索引。
&& &&& &否则，循环因为越界结束，v没有找到，i依然为NIL。
2.1-4 有两个各存放在数组A和B中的n位二进制整数，考虑它们的相加问题。两个整数的和以二进制形式存放在具有(n+1)个元素的数组C中。请给出这个问题的形式化描述，并写出伪代码。
存储说明：最高位存在数组的第一个元素中，最低位存在数组的最后一个元素中。
&& &因为A/B各有n个元素而C有n+1个元素，因此对于任意i(1 ≤ i ≤ n)，A[i]、B[i]和C[i+1]总在相同位（权数）。如下：
BINARY-SUM(A, B, C, n)
for i &- 1 to n+1
do C[i] &- 0
for i &- n to 1
do if A[i] + B[i] + C[i+1] &= 2
then C[i] &- 1
C[i+1] &- (C[i+1] + A[i] + B[i])%2
void binary_sum(const int *arr_a, const int *arr_b, int *arr_c, size_t n)
assert(NULL != arr_a && NULL != arr_b && NULL != arr_c);
for (i = 0; i & n+1; ++i)
arr_c[i] = 0;
if (0 == n)
for (i = n-1; i &= 0; --i) {
if (arr_a[i] + arr_b[i] + arr_c[i+1] &= 2)
arr_c[i] = 1;
arr_c[i+1] = (arr_a[i] + arr_b[i] + arr_c[i+1])%2;
形式化描述：
&& &初始C数组为0。从n到1反向遍历（因为数组第一个元素存储最高为、最后一个元素存储最低位），每次都考虑加法是否需要进位，并设置该位的结果。当循环结束时，C中保存有正确的加法结果。
&& &如果最终的结果依然为n位（最高为没有进位），则C[1]依然为0，对结果没有影响。
&& &初始：
&& &&& &C中各元素为0，加法尚未开始，因此肯定正确。
&& &保持：
&& &&& &对于每一位，当A[i]+b[i]+C[i+1]&=2时，表示需要进位，而此时C[i]肯定为0，因此直接设置为1即可。
&& &&& &对于C[i+1]，如果上次运算有进位，则C[i+1]初始值为1，因此需要考虑A[i]+b[i]+C[i+1]三个位置的值，运算结果为(C[i+1] + A[i] + B[i])%2
&& &退出：
&& &&& &循环结束时，A和B中的所有位已经处理过了，如果最高为有进位，则存储在C[1]中，否则C[1]保持为0，因此结果是正确的。
2.2 算法分析
算法分析：
&& &预测算法运行所需资源。
&& &资源通常是指算法运行时间。
&& &实际中需要考虑的其他资源包括：内存、通信带宽、硬件等。
实现模型：
&& &通用处理器；
&& &随机存取RAM；
&& &均等的指令成本，例如当k较小时（小于等于处理器位宽），2^k可认为在常数时间内完成（移位操作）。
插入排序分析：
&& &T(n) = Θ(n^2)
最坏/好、平均/期望算法运行时间：
&& &最坏/好：算法上/下界（阈值）
&& &平均/期望：随机化分析结果
增长指数：
&& &只统计增长最快项，因为当n增大时，增长最快项是关键。
&& &实际项目中，还需要考虑输入规模和实现的复杂度、可维护性等。
&& &衡量方法Θ
2.2-1 用Θ形式表示函数n^3/-100n+3。
2.2-2 考虑对数组A中的n个数进行排序的问题：首先找出A中的最小元素，并将其与A[1]中元素进行交换。接着，找出A中的次最小元素，并将其与A[2]中的元素进行交换。对A中头n-1个元素继续这一过程。写出这个算法的伪代码，该算法称为选择排序(selection)。对这个算法来说，循环不变式是什么？为什么它仅需要在头n-1个元素上运行，而不是在所有n个元素上运行？以Θ形式写出选择排序的最佳和最坏情况下的运行时间。
SELECTION-SORT(A)
for i &- 1 to length[A]-1
do min &- i
for j &- i+1 to length[A]
do if A[j] & A[min]
then min &-j
exchange(A[i], A[min])
void selection_sort(int *arr, size_t size)
assert(NULL != arr);
for (i = 0; i & ++i) {
for (j = i + 1; j & ++j) {
if (arr[j] & arr[min])
/* exchanges */
if (min != i) {
arr[i] = arr[i]^arr[min];
arr[min] = arr[min]^arr[i];
arr[i] = arr[i]^arr[min];
循环不变式：
&& &初始：
&& &&& &i=1，A[1,i]只包含一个元素即A[1]，因此A[1,i]有序。
&& &保持：
&& &&& &每次i迭加时，总是查找A[i, length[A]]中的最小元素，然后和A[i]交换，因此循环后，A[i]大于等于A[1,i-1]中的任何元素，且小于A[i+1,length[A]]中的任何元素。
&& &&& &因此迭代完成后，A[1,i]依然是有序的。
&& &退出：
&& &&& &当i=length[A]-1时退出。此时A[1,i]所有元素均小于A[length[A]]且有序，因此数组A已排序。
对于选择排序，当前n-1个元素已排序时，剩下的一个元素一定是最大的一个，因此不再需要循环判断。
最佳和最坏运行时间相等，都是Θ(n^2)
2.2-3 再次考察线性查找问题（见练习2.1-3）。在平均情况下，需要检查输入序列中的多少个元素？假定待查找的元素是数组中任何一个元素的可能性是相等的。在最坏情况下又是怎么样？用Θ形式表示的话，线性查找的平均情况和最坏情况运行时间怎样？对你的答案加以说明。
平均需要查找n/2个元素；
最坏需要查找n个元素；
Θ形式的平均和最坏相同，都是Θ(n)。
2.2-4 应如何修该任何一个算法，才能使之具有较好的最佳运行时间？
针对最大概率的输入定制优化一个算法，可获得最佳运行时间。
比如在输入规模很小时，首要考虑算法的常数系数。输入规模很大时，则优先考虑最高项（即Θ结果)。
2.3 算法设计
2.3.1 分治法(Divede-and-Conquer)
递归的把原问题划分成n个较小规模的结构与原问题相似的子问题，递归地解决这些子问题，然后合并结果，就得到原问题的解。
分治模式在每一层上都有三个步骤：分解、解决、合并。
合并排序完全按照上述模式操作，如下：
分解：将n个元素分成各含n/2个问题的子序列。
解决：用合并排序法对子序列递归地排序。
合并：合并两个已排序的子序列以得到排序结果。
在对子序列排序时，其长度为1时认为是已排序的，递归结束。
合并过程如下：
A为待排序数组，n=r-p+1是需要合并的子序列。用∞作为哨兵，它大于任意元素。
MERGE(A, p, q, r)
&& &n1 &- q - p +1
&& &n2 &- r - q
&& &create arrays L[1..n1+1] and R[1..n2+1]
&& &for j &- 1 to n1
&& &&& &do L[i] &- A[p+i-1]
&& &for j &- 1 to n2
&& &&& &do R[j] &- A[q+j]
&& &L[n1+1] &- ∞
&& &R[n2+1] &- ∞
&& &i &- 1
&& &j &- 1
&& &for k &- p to r
&& &&& &do if L[i] ≤ R[j]
&& &&& &&& &then A[k] &- L[i]
&& &&& &&& &&& &i &- i + 1
&& &&& &&& &else A[j] &- R[j]
&& &&& &&& &&& &j &- j + 1
MERGE-SORT(A, p, r)
&& &if p & r
&& &&& &then q &- ?(p+r)/2?
&& &&& &&& &MERGE-SORT(A, p, q)
&& &&& &&& &MERGE-SORT(A, a+1, r)
&& &&& &&& &MERGE(A, p, q, r)
int merge(int *arr, size_t p, size_t q, size_t r)
int i, j, k, n1 = q - p + 1, n2 = r - q, *arr_l, *arr_r;
assert(NULL != arr);
assert(p &= q && q & r);
arr_l = malloc(sizeof(int)*n1);
arr_r = malloc(sizeof(int)*n2);
if (NULL == arr_l || NULL == arr_r) {
/* to free a null pointer is a safe operation */
free(arr_l);
free(arr_r);
return -ENOMEM;
/* we don't use dummy node but to check l and r sub-array */
for (i = 0; i & n1; ++i)
arr_l[i] = arr[p+i];
for (j = 0; j & n2; ++j)
arr_r[j] = arr[q+j+1];
for (i = 0, j = 0, k = i & n1 && j & n2; ++k) {
if (arr_l[i] & arr_r[j]) {
arr[k] = arr_l[i];
arr[k] = arr_r[j];
/* append unused nodes */
while (i & n1) arr[k++] = arr_l[i++];
while (j & n2) arr[k++] = arr_r[j++];
free(arr_l);
free(arr_r);
int merge_sort(int *arr, size_t p, size_t r)
if (p & r) {
size_t q = (p+r)/2;
if (0 == merge_sort(arr, p ,q) && 0 == merge_sort(arr, q+1, r))
return merge(arr, p, q, r);
return -ENOMEM;
C代码需要优化的位置：
C函数merge_sort执行成功时返回0，失败返回-ENOMEM。为了提高程序效率，可以由外部提供辅助空间，这样merge_sort总是成功。更改以后的接口可能是：
&&& void merge_sort(int *arr, size_t p, size_t r, int *arr_helper);
&&& void merge(int *arr, size_t p, size_t q, size_t r, int *arr_helper);
其中arr_helper辅助数组最小需要和arr同等大小。
在merge函数内部，设置arr_l=arr_helper, arr_r=arr_helper+n1即可。
循环不变式：
&& &初始化：
&& &&& &k=p，因此A[p, k-1]是空的，包含0个元素。
&& &&& &又i=j=1，L［i］和R[j]都在各自的数组中，尚未复制到A。
&& &保持：
&& &&& &每次复制时，选择L[i] ≤ R[j]，则L[i]是L和R中尚未复制的最小元素，复制它到A[k]，然后递增k和i，因此A[p,k]中包含最小的k-p+1个元素且有序。
&& &&& &当L中元素全部复制完时，遇到哨兵元素∞，而它比R[j]中任何哨兵以外的元素斗大，因此此后总是复制R[j]的元素并递增j。
&& &&& &当L[i] & R[j]时情况类似。
&& &终止：
&& &&& &此时k=r-p+1，子数组A[p..k-1]已排序。L和R中的所有元素(共n1+n2=r-p+1个)全部拷贝到了A[p,k-1]中。
2.3.2 分治法分析
记分解(Divide)时间为D(n)，合并(Conquer)为C(n)，则：
&& &n = 1：
&& &&& &T(n) = Θ(1)
&& &n & 1：
&& &&& &T(n) = aT(n/b) + D(n) + C(n)
合并排序算法分析：
&& &分解：仅仅需要计算q=(r-p)/2，因此 D(n) = Θ(1)
&& &解决：递归分解为n/2个元素的子数组，因此时间为2T(n/2)。
&& &合并：MERGE的时间复杂度为Θ(n)，因此 C(n) = Θ(n)
&& &因此有：
&& &&& &n = 1:
&& &&& &&& &T(n) = Θ(1)
&& &&& &n & 1:
&& &&& &&& &T(n) = 2T(n/2) + Θ(n)
&& &第四章介绍的主定理对上式做了详细证明。其结果是：
&& &&& &T(n) = Θ(nlgn) (lgn表示log以2为底的n)
&& &因为nlgn的增长速度比n^2要慢很多，因此当输入规模足够大时，合并排序比插入排序的性能要好。
-----------------------------
2.3-1 以图2-4为模型，说明合并排序在输入数组A=〈3，41，52，26，38，57，9，49〉上的执行过程。
2.3-2 改写MERGE过程，使之不使用哨兵元素，而是在一旦数组L或R中的所有元素都被复制回数组A后，就立即停止，再将另一个数组中余下的元素复制回数组A中。
MERGEA(A, p, q, r)
n1 &- q - p +1
n2 &- r - q
create arrays L[1..n1] and R[1..n2]
for j &- 1 to n1
do L[i] &- A[p+i-1]
for j &- 1 to n2
do R[j] &- A[q+j]
while i ≤ n1 and j ≤ n2
do if L[i] ≤ R[j]
then A[k] &- L[i]
i &- i + 1
else A[j] &- R[j]
j &- j + 1
k &- k + 1
if i ≤ n1
then while i ≤ n1
do A[k] &- L[i]
k &- k + 1
i &- i + 1
else while j ≤ n2
do A[k] &- R[j]
k &- k + 1
j &- j + 1
2.3-3 利用数学归纳法证明：当n是2的整数次幂时，递归式
|-- 2T(n/2) + n 如果n=2^k, k&1的解为 T(n) = nlgn
&& &n = 2时，
&& &&& &T(n) = nlgn = 2lg2 = 2 成立。
&& &假定当n=2^k时成立，有：
&& &&& &T(n) = 2^klg(2^k) = (2^k) * k
&& &则当n=2^(k+1)时，有：
&& &&& &T(n) = 2T(n/2) + n
&& &&& &&& &= 2T(2^(k+1)/2) + 2^(k+1)
&& &&& &&& &= 2T(2^k) + 2^(k+1)
&& &&& &&& &= 2 * (2^k) * k + 2^(k+1)
&& &&& &&& &= (2^(k+1)) * k + 2^(k+1)
&& &&& &&& &= (2^(k+1)) * (k+1)
&& &&& &&& &= (2^(k+1)) * lg(2^(k+1))
&& &&& &&& &= nlgn
&& &因此，对于所有的n=2^k, k&=1，递归式均成立。
&& &证毕。
2.3-4 插入排序可以如下改写成一个递归过程：为排序A［1..n］，先递归地排序A［1..n-1］，然后再将A［n］插入到已排序的数组A［1..n-1］中去。对于插入排序的这一递归版本，为它的运行时间写一个递归式。
INSERTION-SORT-RECURSIVE(A, n, k)
then INSERTION-SORT-RECURSIVE(A, n, k-1)
key &- A[k]
for i &- k-1 to 1
do if A[i] & key
then A[i+1] &- A[i]
A[i+1] &- key
2.3-5 回顾一下练习2.1-3中提出的查找问题，注意如果序列A是已排序的，就可以将该序列的中点与v进行比较。根据比较的结果，原序列中有一半就可以不用再做进一步的考虑了。二分查找（binary search）就是一个不断重复这一查找过程的算法，它每次都将序列余下的部分分成两半，并只对其中的一半做进一步的查找。写出二分查找算法的伪代码，可以是迭代的，也可以是递归的。说明二分查找算法的最坏情况运行时间为什么是Θ(lgn)。
迭代版本：
BINARY-SEARCH-ITERATE(A, v)
high &- length[A]
while low ≤ high
do mid &- ?(low + high)/2?
if A[mid] = v
then return mid
elif A[mid] & v
then low &- mid + 1
else high &- mid - 1
return NIL
注意，当查找到时，设置low=high+1，因此下次循环检测时循环结束，并且idx已被设置为正确值。
递归版本：
BINARY-SEARCH-RECURSIVE(A, v, low, high)
if low & high
then return NIL
mid &- ?(low + high)/2?
if A[mid] = v
then return mid
elif A[mid] & v
then return BINARY-SEARCH-RECURSIVE(A, v, mid+1, high)
else return BINARY-SEARCH-RECURSIVE(A, v, low, mid-1)可知，二分查找时间复杂度满足
&& &T(n) = 2T(n/2) + Θ(1)
&& &T(n) = Θ(lgn)
2.3-6 观察一下2.1节中给出的INSERTION-SORT过程，在第5~7行的while循环中，采用了一种线性查找策略，在已排序的子数组A［1..j- 1］中（反向）扫描。是否可以改用二分查找策略（见练习2.3.5），来将插入排序的总体最坏情况运行时间改善至Θ(nlgn)？
完成了一定程度上的优化，但依然不满足Θ(nlgn)，因为需要移动元素的平均个数依然是n/2，因此还是Θ(n^2)。
*2.3-7 请给出一个运行时间为Θ(nlgn)的算法，使之能在给定一个由n个整数构成的集合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。
考虑到目前只学习了合并排序和二分查找，因此用这两种方法实现解决该问题，如下：
SEARCH－SUM(S, x)
MERGE-SORT(S, 0, length[S])
for i &- 0 to length[S]
do v &- x - S[i]
if BINARY-SEARCH-ITERATE(S, v) != NIL
then return true
return false分析：
MERGE-SORT时间复杂度为Θ(nlgn)，循环执行n次，每次BINARY-SEARCH-ITERATE的时间复杂度为Θ(lgn)，所以循环体的时间复杂度是Θ(nlgn)。
因此，SEARCH-SUM的时间复杂度为Θ(nlgn)。
------------------------
2-1在合并排序中对小数组采用插入排序
尽管合并排序的最坏情况运行时间为Θ(nlgn)，插入排序的最坏情况运行时间为Θ(n^2)，但插入排序中的常数因子使得它在n较小时，运行得要更快一些。因此，在合并排序算法中，当子问题足够小时，采用插入排序就比较合适了。考虑对合并排序做这样的修改，即采用插入排序策略，对n/k个长度为k的子列表进行排序，然后，再用标准的合并机制将它们合并起来，此处k是一个待定的值。
a)证明在最坏情况下，n/k个子列表（每一个子列表的长度为k）可以用插入排序在Θ(nk)时间内完成排序。
b)证明这些子列表可以在Θ(nlg(n/k))最坏情况时间内完成合并。
c)如果已知修改后的合并排序算法的最坏情况运行时间为Θ(nk+nlg(n/k)),要使修改后的算法具有与标准合并排序算法一样的渐近运行时间，k的最大渐近值（即Θ形式）是什么（以n的函数形式表示）？
d)在实践中，k的值应该如何选取？
a) 每个子列表长度为k，因此每个子列表插入排序的时间为Θ(k^2)。共有n/k个子列表，故总的时间为Θ(k^2)*(n/k) = Θ(nk)
b) 此时共需合并n/k次（因为分解了n/k次），每次合并的时间为Θ(n)，故所有合并的时间为Θ(nlg(n/k))
c) 问题等价于求解 Θ(nk + nlg(n/k)) = Θ(nlgn)。其最大渐近值为lgn。
d) 这是个实验问题，应该在k的合法范围内测试可能的k，用T-INSERTION-SORT(k)表示k个元素的插入排序时间，T-MERGE-SORT(k)表示k个元素的合并排序时间。该问题等价于测试求解T-INSERTION-SORT(k)/T-MERGE-SORT(k)比值最小的k值。
2-2冒泡排序算法的正确性
冒泡排序（bubblesort）算法是一种流行的排序算法，它重复地交换相邻的两个反序元素。
BUBBLESORT(A)
&& &1 for i &- 1 to length[A]
&& &2&& &do for j &- length[A] downto i + 1
&& &3&& &&& &do if A[j] & A[j-1]
&& &4&& &&& &&& &then exchange A[j] &-& A[j-1]
a) 设A′表示BUBBLESORT(A)的输出。为了证明BUBBLESORT是正确的，需要证明它能够终止，并且有：
&&& A'[1] ≤ A'[2] ≤ ... ≤ A'[n]&&&&&&&&&&&&&&&&&&&& (2.3)
&& 其中n=length［A］。为了证明BUBBLESORT的确能实现排序的效果，还需要证明什么？
下面两个部分将证明不等式（2.3）。
b)对第2~4行中的for循环，给出一个准确的循环不变式，并证明该循环不变式是成立的。在证明中应采用本章中给出的循环不变式证明结构。
c)利用在b)部分中证明的循环不变式的终止条件，为第1~4行中的for循环给出一个循环不变式，它可以用来证明不等式(2.3)。你的证明应采用本章中给出的循环不变式的证明结构。
d)冒泡排序算法的最坏情况运行时间是什么？比较它与插入排序的运行时间。
a) A中所有的元素都在A'中，或者说A中的任意元素在A'中存在且唯一(一一对应)。
b) 冒泡排序中，需要证明子数组A[j-1..n]的最小元素为A[j-1]。 初始、保持、终止三元素描述如下：
&& &j=n，子数组为A[j-1..n]=A[n-1..n]有两个元素。在循环内部，通过条件交换语句，可以保证A[n-1] & A[n]成立。因此A[j-1]是A[j-1..n]中的最小元素。
&& &每次迭代开始时，A[j]是A[j..n]中的最小元素。
&& &在迭代操作中，当A[j] & A[j-1]时交换，因此总有A[j-1] & A[j]。
&& &可知，本次迭代操作完成后，A[j-1]一定是A[j-1..n]中的最小元素。
&& &j=i+1时退出，因此结束时，A[i]一定是A[i..n]中的最小元素。
c) 描述如下：
&& &i=1，是A中的第一个元素，因此内部循环完成后，可以保证A[1]中保存A[1..n]的最小元素。
&& &每次递增i时，执行内部循环，因此A[i]中保存A[i..n]中的最小元素。
&& &可知每次内部循环完成后，都有 A[1] ≤ A[2] ≤ ... ≤ A[i]
&& &i=length[A]时终止，此时有 A[1] ≤ A[2] ≤ ... ≤ A[n]。
冒泡排序最坏和最好运行时间均为Θ(n^2)；
插入排序的最坏运行时间为Θ(n^2)，但是最好运行时间为Θ(n)；
排序前A所有元素已经有序时，插入排序达到最好运行时间。
2.3 霍纳规则的正确性
以下的代码片段实现了用于计算多项式
&& &P(x) = a0 + x(a1 + x(a2 + ... + x(an-1 + xan)...))
的霍纳规则（Horner's rule）。
给定系数a0, a1, ..., an-1, an以及x的值，有：
while i ≥ 0
do y &- ai + x*y
i &- i - 1a)这一段实现霍纳规则的代码的渐近运行时间是什么？
b)写出伪代码以实现朴素多项式求值（naive polynomial-evaluation）算法，它从头开始计算多项式的每一个项。这个算法的运行时间是多少？它与实现霍纳规则的代码段的运行时间相比怎样？
c)证明以下给出的是针对第3~5行中while循环的一个循环不变式：
在第3~5行中while循环每一轮迭代的开始，有：
&& &y = ai+1 * x + ai+2 * x^2 + ... + ai+1+k * x^k
不包含任何项的和视为等于0。你的证明应遵循本章中给出的循环不变式的证明结构，并应证明在终止时，有
y = a0 + a1*x + a2*x2 + ... + an*x^n
d)最后证明以上给出的代码片段能够正确地计算由系数a0, a1, ..., an刻划的多项式。
b) 朴素多项式求值：
NATIVE-POLYNOMIAL-EVALUATION(A, x)
for i &- 0 to length[A]
do for j &- 1 to i
do v &- v*x
y &- y + A[i]*v
return y算法运行时间为Θ(n^2)。而霍纳规则代码段时间复杂度为Θ(n)。因此，该算法的时间耗费是霍纳规则代码段的Θ(n)倍。
由于0从0到n-(i+1)，因此有：
y = Σ ak+i+1 * x^k
& = ak+i+1 + ak+i+2 * x + ... + an * x^(n-(i+1))
霍纳规则代码段循环不变式证明如下：
&& &i=n，y[n] = 0，迭代开始时，循环后有y[n] = a[n]。
&& &对于任意 0 ≤ i ≤ n，循环后有：
&& &&& &y[i] = a[i] + y[i+1] * x = a[i] + (a[i+1] * x + a[i+2] * x + ... + a[n] * x^(n-(i+1))) * x
&& &&& &&& & = a[i] + a[i+1] * x + a[i+2] * x^2 + ... + a[n] * x^(n-i)
&& &i小于0时终止，此时有 y[0] = a[0] + a[1] * x + a[2] * x^2 + a[n] * x^n
证明和y = Σ a[k+i+1] * x^k的关系：
&& &k 从0到n-(i+1)，等价于 0 ≤ k ≤ n-(i+1)。因此
&& &&& &y = Σ a[k+i+1] * x^k
&& &&& &&& &= a[i+1] + a[i+2] * x + ... + a[n-(i+1)+i+1] * x^(n-i)
&& &&& &&& &= a[i+1] + a[i+2] * x + ... + a[n] * x^(n-i)
&& &由于i+1循环之后和i循环之前的值相等，用y'[i]表示i循环之前的值，则有：
&& &&& &y'[i] = y[i+1]
&& &霍纳规则循环不变式的结果表明：
&& &&& &y[i] = a[i] + a[i+1] * x + a[i+2] * x^2 + ... + a[n] * x^(n-i)
&& &因此有：
&& &&& &y'[i] = y[i+1] = a[i+1] + a[i+2] * x + ... + a[n] * x^(n-(i+1))
&& &令k=n-(i+1)，则n=k+i+1，所以：
&& &&& &y'[i] = a[i+1] + a[i+2] * x + ... + a[k+i+1] * x^(k+i+1-(i+1))
&& &&& &&& &&& &= a[i+1] + a[i+2] * x + ... + a[k+i+1] * x^k
&& &用y表示y'[i]，则有：
&& &&& &y = a[i+1] + a[i+2] * x + ... + a[k+i+1] * x^k
&& &&& &&& &= Σ a[k+i+1] * x^k
&& &其中 k从0到n-(i+1)
&& &证毕。
2.4 逆序对
设A［1..n］是一个包含n个不同数的数组。如果i&j且A[i]&A[j]，则(i,j)就称为A中的一个逆序对（inversion）。
a)列出数组〈2,3,8,6,1〉的5个逆序。
b)如果数组的元素取自集合{1, 2, ..., n}，那么，怎样的数组含有最多的逆序对？它包含多少个逆序对？
c)插入排序的运行时间与输入数组中逆序对的数量之间有怎样的关系？说明你的理由。
d）给出一个算法，它能用Θ(nlgn)的最坏情况运行时间，确定n个元素的任何排列中逆序对的数目。（提示：修改合并排序）
数组从大到小有序排列时，逆序对最多，为n(n-1)/2个。
逆序对增加时，插入排序时间增加。
没有逆序对时，插入排序时间最少，为Θ(n)。
逆序对最多时，插入排序时间最多，为Θ(n^2)。
初始化count为0，对数组执行合并排序，在合并(MERGE)操作中，只要i&j且L[i] & R[j]，则递增统计计数count。合并排序完成后count值为逆序对的数目。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：43399次
排名：千里之外
原创：46篇
评论：13条
(1)(3)(1)(4)(2)(7)(10)(1)(13)(1)(1)(1)(1)