书名：计算机算法设计与分析习题解答（第2版）pdf/doc/txt格式电子书下载

推荐语：

作者：王晓东著

出版社：电子工业出版社

出版时间：2012-06-01

书籍编号：30466849

ISBN：9787121161346

正文语种：中文

字数：73989

版次：2

所属分类：教材教辅-大学

版权信息

书名：计算机算法设计与分析习题解答（第2版）

作者：王晓东

ISBN：9787121161346

版权所有 · 侵权必究

前言

一些著名的计算机科学家在有关计算机科学教育的论述中认为，计算机科学是一种创造性思维活动，其教育必须面向设计。计算机算法设计与分析正是一门面向设计，且处于计算机学科核心地位的教育课程。通过对计算机算法系统的学习与研究，理解和掌握算法设计的主要方法，培养对算法的计算复杂性进行正确分析的能力，为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础，对从事计算机系统结构、系统软件和应用软件研究与开发的科技工作者是非常重要和必不可少的。

电子工业出版社出版的《计算机算法设计与分析（第4版）》是普通高等教育“十一五”国家级规划教材，它是根据教育部高教司主持评审的《中国计算机科学与技术学科教程2002》以及ACM和IEEE/CS CC2001组织编写的教材，在内容选材、深度把握、系统性和可用性方面进行了精心设计，力图适合高校本科生教学对学时数和知识结构的要求。本书是与《计算机算法设计与分析（第4版）》配套的辅助教材，对该书中的习题做了解答或给出了解题思路提示。

算法设计与分析是计算学科的9个主科目之一，而且在整个学科知识体系中具有学科核心的重要地位，它充分体现了计算机科学方法论的理论、抽象和设计3个过程，知识面较宽，且有一定的深度；算法设计与分析课程需要反复再现计算机科学中用到的大问题的复杂性、效率、抽象的层次、重用、折中等带有普遍性的概念。根据作者多年的教学经验，算法设计与分析课程教学有以下3个特点，这使许多学生感到学习相当困难。

（1）按照《中国计算机科学与技术学科教程2002》以及ACM和IEEE/CS CC2001的要求，算法设计与分析课程教学包括的知识点多，内容十分丰富，学习量大。

（2）课程内容理论性很强，对学生的抽象思维能力和逻辑推理能力要求较高。

（3）课程内容还有很强的实践性，要求学生灵活运用所学到的算法设计策略解决实际问题。

教材中的课后习题能在很大程度上解决上面所说的困难。《计算机算法设计与分析（第4版）》所配备的习题正是为此目的而设计的。教材出版后，许多读者纷纷要求给出习题解答和提示。为了让使用《计算机算法设计与分析（第4版）》作为教材的师生在广度和深度的各个层面更深刻地理解理论、抽象和设计这3个过程以及重复出现的12个基本概念（绑定、大问题的复杂性、概念和形式模型、一致性和完备性、演化、效率、抽象层次、按空间排序、按时间排序、重用、安全性、折中的结论），作者根据多年的教学经验编写了这本辅助教材，旨在让使用该书的教师更容易教，学生更容易学。为了便于对照阅读，本书的章序与《计算机算法设计与分析（第4版）》保持一致，且一一对应。

本书的内容是对教材《计算机算法设计与分析（第4版）》的扩展，一些在教材中无法讲述的较深入的主题通过习题的形式展现出来。为了提高学生灵活运用算法设计策略解决实际问题的能力，本书将原教材中的许多习题改造成算法实现题，要求学生不仅设计出解决具体问题的算法，而且能上机实现。其中很多题目使用了多种不同解法，体现了算法的灵活性和适用性。根据作者多年的教学实践，这类算法实现题的教学效果非常好。

本书内容丰富，理论联系实际，可作为高等学校计算机科学与技术、软件工程、信息安全、信息与计算科学等专业本科生和研究生学习计算机算法设计的辅助教材，也是工程技术人员和自学者的参考书。

作者还结合国家精品课程建设，进行了教材的立体化开发，包括主教材、习题解答、电子课件和教学网站等资源。作者的教学网站网址是：http：//www.algorithm.fzu.edu.cn，作者的E-mail地址是：wangxd＠fzu.edu.cn。欢迎广大读者访问教学网站并提出宝贵意见。

本书提供的教学资源包含各章算法实现题的题目、测试数据和答案。共有12个子目录，包括：ch1，ch2，…，ch8，midexam1，midexam2，finalexam1，finalexam2。每章的每个算法实现题都对应一个子目录，其中的test子目录中是测试数据，answer子目录中是相应的答案。midexam1和midexam2目录中是两套期中试卷。finalexam1和finalexam2目录中是两套期终试卷。本书主教材提供电子课件，需要者可登录华信教育资源网http：//www.hxedu.com.cn免费注册下载。算法设计的实现平台是Microsoft Visual Studio 6.0或Microsoft Visual Studio.NET。采用面向对象的C++语言作为算法描述手段。

在本书编写过程中，福州大学“211工程”计算机与信息工程重点学科实验室提供了优良的设备与工作环境。电子工业出版社负责本书编辑出版工作的全体同仁为本书的出版付出了大量辛勤劳动，他们认真细致，一丝不苟的工作精神保证了本书的出版质量。在此，谨向每位曾经关心和支持本书编写工作的各方面人士表示衷心的谢意！

作者

第1章 算法概述

算法分析题1

1-1 函数的渐近表达式

求下列函数的渐近表达式：

3n²+10n；n²/10+2ⁿ；21+1/n；logn³；10log3ⁿ。

分析与解答：

3n²+10n=O（n²）；　logn³=O（logn）；

n²/10+2ⁿ=O（2ⁿ）；　10log3ⁿ=O（n）。

21+1/n=O（1）；

1-2 O（1）和O（2）的区别

试论O（1）和O（2）的区别。

分析与解答：根据符号O的定义易知O（1）=O（2）。用O（1）或O（2）表示同一个函数时，差别仅在于其中的常数因子。

1-3 按渐近阶排列表达式

按照渐近阶从低到高的顺序排列以下表达式：4n²，logn，3ⁿ，20n，2，n^2/3。又n！应该排在哪一位?

分析与解答：按渐近阶从低到高，函数排列顺序如下：2，logn，n^2/3，20n，4n²，3ⁿ，n！。

1-4 算法效率

（1）假设某算法在输入规模为n时的计算时间为T（n）=3×2ⁿ。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题?

（2）若上述算法的计算时间改进为T（n）=n²，其余条件不变，则在新机器上用t秒时间能解输入规模为多大的问题?

（3）若上述算法的计算时间进一步改进为T（n）=8，其余条件不变，那么在新机器上用t秒时间能解输入规模为多大的问题?

分析与解答：

（1）设新机器用同一算法在t秒内能解输入规模为n1的问题。因此有：t=3×2ⁿ=3×2ⁿ¹/64，解得n1=n+6。

（2）n1²=64n²⇒n1=8n。

（3）由于T（n）=常数，因此算法可解任意规模的问题。

1-5 硬件效率

硬件厂商XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n²，n³和n！的各算法，若用ABC公司的计算机在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题?

分析与解答：

n′=100n　n′³=100n³⇒n′==4.64n

n′²=100n²⇒n′=10n　n′！=100n！⇒n′＜n+log100=n+6.64

1-6 函数渐近阶

对于下列各组函数f（n）和g（n），确定f（n）=O（g（n））或f（n）=Ω（g（n））或f（n）=θ（g（n）），并简述理由。

（1）f（n）=logn²；g（n）=logn+5　（5）f（n）=10；　g（n）=log10

（2）f（n）=logn²；　g（n）=　（6）f（n）=log²n；g（n）=logn

（3）f（n）=n；　g（n）=log²n　（7）f（n）=2ⁿ；　g（n）=100n²

（4）f（n）=nlogn+n；g（n）=logn　（8）f（n）=2ⁿ；　g（n）=3ⁿ

分析与解答：

（1）logn²=θ（logn+5）　（5）10=θ（log10）

（2）logn²=O）　（6）log²n=Ω（logn）

（3）n=Ω（log²n）　（7）2ⁿ=Ω（100n²）

（4）nlogn+n=Ω（logn）　（8）2ⁿ=O（3ⁿ）

1-7 n！的阶

证明：n！=o（nⁿ）。

分析与解答：Stirling’s approximation：

1-8 3n+1问题

下面的算法段用于确定n的初始值。试分析该算法段所需计算时间的上界和下界。

分析与解答：该算法表述的是著名的3n+1问题。在最坏情况下，该算法的计算时间下界显然为Ω（logn）。

算法的计算时间上界至今未知。算法是否在有限时间内结束，至今还是一个悬而未决的问题。日本学者米田信夫曾对10¹³内的所有自然数验证上述算法均在有限步结束。人们猜测，对所有自然数，上述算法均在有限步结束，但无法给出理论证明，因此也无法分析上述算法的计算时间上界。这个猜测就成为著名的3n+1猜想，也称为Collatz猜想。

1-9 平均情况下的计算时间复杂性

证明：如果一个算法在平均情况下的计算时间复杂性为θ（f（n）），则该算法在最坏情况下所需的计算时间为Ω（f（n））。

分析与解答：

因此，T_max（N）=Ω（T_avg（N））=Ω（θ（f（n）））=Ω（f（n））。

算法实现题1

1-1 统计数字问题

★问题描述：一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06或006等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，…，9。

★算法设计：给定表示书的总页码的十进制整数n（1≤n≤10⁹）。计算书的全部页码中分别用到多少次数字0，1，2，…，9。

★数据输入：输入数据由文件名为input.txt的文本文件提供。每个文件只有1行，给出表示书的总页码的整数n。

★结果输出：将计算结果输出到文件output.txt中。输出文件共有10行，在第k行输出页码中用到数字k-1的次数，k=1，2，…，10。

分析与解答：考察由0，1，2，…，9组成的所有n位数。从n个0到n个9共有10ⁿ个n位数。在这10ⁿ个n位数中，0，1，2，…，9每个数字使用次数相同，设为f（n）。f（n）满足如下递归式：

由此可知，f（n）=n10^n-1。

据此，可从高位向低位进行统计，再减去多余的0的个数即可。

1-2 字典序问题

★问题描述：在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A由26个小写英文字母组成A={a，b，…，z}。该字母表产生的升序字符串是指字符串中字母从左到右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1次。例如，a，b，ab，bc，xyz等字符串都是升序字符串。现在对字母表A产生的所有长度不超过6的升序字符串按照字典序排列并编码如下。

对于任意长度不超过6的升序字符串，迅速计算出它在上述字典中的编码。

★算法设计：对于给定的长度不超过6的升序字符串，计算它在上述字典中的编码。

★数据输入：输入数据由文件名为input.txt的文本文件提供。文件的第1行是一个正整数k，表示接下来共有k行。在接下来的k行中，每行给出一个字符串。

★结果输出：将计算结果输出到文件output.txt中。文件共有k行，每行对应于一个字符串的编码。

分析与解答：考察一般情况下长度不超过k的升序字符串。

设以第i个字符打头的长度不超过k的升序字符串个数为f（i，k），长度不超过k的升序字符串总个数为g（k），则g（k）=。易知

一般情况下有

据此可计算出每个升序字符串的编码。

1-3 最多约数问题

★问题描述：正整数x的约数是能整除x的正整数。正整数x的约数个数记为div（x）。例如，1，2，5，10都是正整数10的约数，且div（10）=4。设a和b是2个正整数，a≤b，找出a和b之间约数个数最多的数x。

★算法设计：对于给定的2个正整数a≤b，计算a和b之间约数个数最多的数。

★数据输入：输入数据由文件名为input.txt的文本文件提供。文件的第1行有2个正整数a和b。

★结果输出：若找到的a和b之间约数个数最多的数是x，则将div（x）输出到文件output.txt中。

分析与解答：设正整数x的质因子分解为

则

div（x）=（N₁+1）（N₂+1）…（N_k+1）

搜索区间［a，b］中数的质因子分解。

primes产生质数。

search搜索最多约数。

实现算法的主函数如下。

1-4 金币阵列问题

★问题描述：有m×n（m≤100，n≤100）枚金币在桌面上排成一个m行n列的金币阵列。每一枚金币或正面朝上，或背面朝上。用数字表示金币状态，0表示金币正面朝上，1表示金币背面朝上。

金币阵列游戏的规则是：

（1）每次可将任一行金币翻过来放在原来的位置上；

（2）每次可任选2列，交换这2列金币的位置。

★算法设计：给定金币阵列的初始状态和目标状态，计算按金币游戏规则，将金币阵列从初始状态变换到目标状态所需的最少变换次数。

★数据输入：由文件input.txt给出输入数据。文件中有多组数据。文件的第1行有1个正整数k，表示有k组数据。每组数据的第1行有2个正整数m和n。以下的m行是金币阵列的初始状态，每行有n个数字表示该行金币的状态，0表示正面朝上，1表示背面朝上。接着的m行是金币阵列的目标状态。

★结果输出：将计算出的最少变换次数按照输入数据的次序输出到文件output.txt。相应数据无解时输出-1。

分析与解答：枚举初始状态每一列变换为目标状态第1列的情况。算法描述如下。

其中，trans1模拟行翻转变换，trans2模拟列交换变换。

1-5 最大间隙问题

★问题描述：最大间隙问题：给定n个实数x₁，x₂，…，x_n，求这n个数在实轴上相邻2个数之间的最大差值。假设对任何实数的下取整函数耗时O（1），设计解最大间隙问题的线性时间算法。

★算法设计：对于给定的n个实数x₁，x₂，…，x_n，计算它们的最大间隙。

★数据输入：输入数据由文件名为input.txt的文本文件提供。文件的第1行有1个正整数n。接下来的1行中有n个实数x₁，x₂，…，x_n。

★结果输出：将找到的最大间隙输出到文件output.txt中。

分析与解答：用鸽舍原理设计最大间隙问题的线性时间算法如下。

其中，mini和maxi分别计算数组中最小元素和最大元素的下标。

由于下取整函数耗时O（1），故循环体内的运算耗时O（1）。因此，整个算法耗时O（n）。即算法maxgap是求最大间隙问题的线性时间算法。注意到在代数判定树计算模型下，Ω（nlogn）是最大间隙问题的一个计算时间下界。这意味着在代数判定树的计算模型下，最大间隙问题是不可能有线性时间算法的。在此题中假设下取整函数耗时O（1），实际上这可以看作是在代数判定树模型中，将下取整运算作为基本运算增加到原有的基本运算集中，从而使代数判定树计算模型的计算能力得到增强。因而可以在线性时间内解最大间隙问题。

第2章 递归与分治策略

算法分析题2

2-1 Hanoi塔问题的非递归算法

证明Hanoi塔问题的递归算法与非递归算法实际上是一回事。

分析与解答：Hanoi塔问题的递归算法：

主教材中所述非递归算法的目的塔座不确定。当n为奇数时，目的塔座是B，按顺时针方向移动；而当n为偶数时，目的塔座为C，按反时针方向移动。为确定起见，规定目的塔座为B。Hanoi塔问题的非递归算法可描述如下。

下面用数学归纳法证明递归算法和非递归算法产生相同的移动序列。

当n=1和n=2时容易直接验证。设当k≤n-1时，递归算法和非递归算法产生完全相同的移动序列。考察k=n的情形。

将移动分为顺时针移动（C）、逆时针移动（CC）和非最小圆盘塔座间的移动（O）三种情况。

当n为奇数时，顺时针非递归算法产生的移动序列为C，O，C，O，…，C；逆时针非递归算法产生的移动序列为CC，O，CC，O，…，CC。

当n为偶数时，顺时针非递归算法产生的移动序列为CC，O，CC，O，…，CC；逆时针非递归算法产生的移动序列为C，O，C，O，…，C。

（1）当n为奇数时，顺时针递归算法hanoi（n，A，B，C）产生的移动序列为

hanoi（n-1，A，C，B）产生的移动序列，O，hanoi（n-1，C，B，A）产生的移动序列

其中，hanoi（n-1，A，C，B）和hanoi（n-1，C，B，A）均为偶数圆盘逆时针移动问题。由数学归纳法知，它们产生的移动序列均为C，O，C，O，…，C。因此，hanoi（n，A，B，C）产生的移动序列为C，O，C，O，…，C。

（2）当n为偶数时，顺时针递归算法hanoi（n，A，B，C）产生的移动序列为

hanoi（n-1，A，C，B）产生的移动序列，O，hanoi（n-1，C，B，A）产生的移动序列

其中，hanoi（n-1，A，C，B）和hanoi（n-1，C，B，A）均为奇数圆盘逆时针移动问题。由数学归纳法知，它们产生的移动序列均为CC，O，CC，O，…，CC。因此，hanoi（n，A，B，C）产生的移动序列为CC，O，CC，O，…，CC。

当n为奇数和偶数时的逆时针递归算法也类似。

由数学归纳法可知，递归算法和非递归算法产生相同的移动序列。

2-2 7个二分搜索算法

下面的7个算法与主教材第2章中的二分搜索算法BinarySearch略有不同。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算法的正确性证明。

分析与解答：（1）与主教材中的算法BinarySearch相比，数组段左、右游标left和right的调整不正确，导致陷入死循环。

（2）与主教材中的算法BinarySearch相比，数组段左、右游标left和right的调整不正确，导致当x=a［n-1］时返回错误。

（3）与正确算法BinarySearch5相比，数组段左、右游标left和right的调整不正确，导致当x=a［n-1］时返回错误。

（4）与正确算法BinarySearch5相比，数组段左、右游标left和right的调整不正确，导致陷入死循环。

（5）算法正确，且当数组中有重复元素时，返回满足条件的最右元素。

（6）与正确算法BinarySearch5相比，数组段左、右游标left和right的调整不正确，导致当x=a［n-1］时返回错误。

（7）与正确算法BinarySearch5相比，数组段左、右游标left和right的调整不正确，导致当x=a［0］时陷入死循环。

2-3 改写二分搜索算法

设a［0：n-1］是已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

分析与解答：改写二分搜索算法如下。

2-4 大整数乘法的O（nm^log（3/2））算法

给定2个大整数u和v，它们分别有m位和n位数字，且m≤n。用通常的乘法求uv的值需要O（mn）时间。可以将u和v均看作是有n位数字的大整数，用主教材第2章介绍的分治法，在O（n^log3）时间内计算uv的值。当m比n小得多时，用这种方法就显得效率不够高。试设计一个算法，在上述情况下用O（nm^log（3/2））时间求出uv的值。

分析与解答：当m比n小得多时，将v分成n/m段，每段m位。计算uv需要n/m次m位乘法运算。每次m位乘法可以用主教材中的分治法计算，耗时O（m^log3）。因此，算法所需的计算时间为O（（n/m）m^log3）=O（nm^log（3/2））。

2-5 5次n/3位整数的乘法

在用分治法求两个n位大整数u和v的乘积时，将u和v都分割为长度为n/3位的3段。证明可以用5次n/3位整数的乘法求得uv的值。按此思想设计一个求两个大整数乘积的分治算法，并分析算法的计算复杂性（提示：n位的大整数除以一个常数k可以在θ（n）时间内完成。符号θ所隐含的常数可能依赖于k）。

分析与解答：这个问题有更一般的解。将两个n位大整数u和v都分割为长度为n/m位的m段，可以用2m-1次n/m位整数的乘法求得uv的值。

事实上，设x=2^n/m，可以将u和v及其乘积w=uv表示为

u=u₀+u₁x+…+u_m-1x^m-1

v=v₀+v₁x+…+v_m-1x^m-1

w=uv=w₀+w₁x+w₂x²+…+w_2m-2x^2m-2

将u，v和w都看作关于变量x的多项式，并取2m-1个不同的数x₁，x₂，…，x_2m-1代入多项式可得

用矩阵形式表示为

设

则

式中，w（x_i）=u（x_i）v（x_i）是2个n/m位数的乘法运算，共有2m-1个乘法。其他均为加减法或数乘运算。

下面用m=3的具体例子来说明。

设x=2^n/3，可以将u和v及其乘积w=uv表示为

u=u₀+u₁x+u₂x²

v=v₀+v₁x+v₂x²

w=uv=w₀+w₁x+w₂x²+w₃x³+w₄x⁴

取5个数x₁，x₂，…，x₅如下：

x₁=0，x₂=-2，x₃=2，x₄=-1，x₅=1

代入多项式得

a=w（x₁）=u₀v₀

b=w（x₂）=（u₀-2u₁+4u₂）（v₀-2v₁+4v₂）

c=w（x₃）=（u₀+2u₁+4u₂）（v₀+2v₁+4v₂）

d=w（x₄）=（u₀-u₁+u₂）（v₀-v₁+v₂）

解得

由x₁，x₂，…，x₅的不同取法，可得到不同的分解方法。

按此分解设计的求两个n位大整数乘积的分治算法需要5次n/3位整数乘法。分割及合并步所需的加减法和数乘运算时间为O（n）。设T（n）是算法所需的计算时间，则

由此可得T（n）=O（n^log₃5）。

在一般情况下，将两个n位大整数u和v都分割为长度为n/m位的m段，可以用2m-1次n/m位整数的乘法求得uv的值。由此设计出的求两个n位大整数乘积的分治算法需要2m-1次n/m位整数乘法。分割及合并步所需的加减法和数乘运算时间为O（n）。因此其计算时间T（n）满足：

解此递归式可得T（n）=O（n^{log_m（2m-1）}）。

2-6 矩阵乘法

对任何非零偶数n，总可以找到奇数m和正整数k，使得n=m2^k。为了求出两个n阶矩阵的乘积，可以把一个n阶矩阵分成m×m个子矩阵，每个子矩阵有2^k×2^k个元素。当需要求2^k×2^k的子矩阵的积时，使用Strassen算法。设计一个传统方法与Strassen算法相结合的矩阵相乘算法，对任何偶数n，都可以求出两个n阶矩阵的乘积。并分析算法的计算时间复杂性。

分析与解答：将n阶矩阵分块为m×m的矩阵。用传统方法求两个m阶矩阵的乘积需要计算O（m³）次2个2^k×2^k矩阵的乘积。用Strassen矩阵乘法计算两个2^k×2^k矩阵的乘积需要的计算时间为O（7^k），因此算法的计算时间为O（7^km³）。

2-7 多项式乘积

设P（x）=a₀+a₁x+…+a_dx^d是一个d次多项式。假设已有一个算法能在O（i）时间内计算一个i次多项式与一个一次多项式的乘积，以及一个算法能在O（ilogi）时间内计算两个i次多项式的乘积。对于任意给定的d个整数n₁，n₂，…，n_d，用分治法设计一个有效算法，计算出满足P（n₁）=P（n₂）=…=P（n_d）=0且最高次项系数为1的d次多项式P（x），并分析算法的效率。

分析与解答：

用分治法将d次多项式转化为两个d/2次多项式的乘积。

设用此算法计算d次多项式所需计算时间为T（d），则T（d）满足如下递归式：

解此递归式可得T（d）=O（dlog²d）。

2-8 O（1）空间子数组换位算法

设a［0：n-1］是一个有n个元素的数组，k（1≤k≤n-1）是一个非负整数。试设计一个算法将子数组a［0：k-1］与a［k+1：n-1］换位。要求算法在最坏情况下耗时O（n），且只用到O（1）的辅助空间。

分析与解答：

算法1：循环换位算法

（1）向前循环换位

（2）向后循环换位

（3）选择较小的数组块进行循环

在最坏情况下，算法所需的元素移动次数为min{k，n-k}·（n+1）。算法仅用到一个辅助单元tmp，因此算法只用到O（1）的辅助空间。当k=n/2时，计算时间非线性。

算法2：3次反转算法

将数组块a［i：j］反转的算法如下。

设a［0：k-1］为U，a［k：n-1］为V，换位算法要求将UV变换为VU。3次反转算法先将U反转为U^-1，再将V反转为V^-1，最后将U^-1V^-1反转为VU。

3次反转算法用了次数组单元交换运算。每个数组单元交换运算需要3次元素移动。因此在最坏情况下，3次反转算法用了3n

....