Chapter 2-4 程序性能分析、渐进记法和性能测试.

Presentation on theme: "Chapter 2-4 程序性能分析、渐进记法和性能测试."— Presentation transcript:

1 Chapter 2-4 程序性能分析、渐进记法和性能测试

2 算法性能分析 算法正确性分析 算法的性能分析 基于算法的输入和输出，利用数学的方法证明对任意输入，算法计算的结果都是我们想要的输出
算法的最长执行时间和最大的内存空间占有，即最坏情况下的情形，或平均。

3 评价程序执行的两个测度 1) 时间复杂性: (T(n)) 2) 空间复杂性 (S(n))
一个算法的时间复杂性是以算法中基本操作的步数衡量的。 2) 空间复杂性 (S(n)) 一个程序在运行时所需内存大小为测度 n 是问题的尺寸（元素的个数）,基本操作是指主要的运算，并且是最耗时的运算子

4 时间复杂性分析 选择一个最基本的操作，希望能找到一个以尺寸n为自变量的渐进函数来刻画所需要的基本操作步数的上限和下限

5 空间复杂性分析 静态部分 程序所用变量所需的内存数量,如n*n矩阵,需要 n2 *T 类型尺寸空间 (静态定义）
程序运行时动态最大可要求的空间（动态申请） 递归程序、临时申请变量的空间 我们希望能找到一个以尺寸n为自变量的渐进函数描述所需空间的上界、下界。

6 渐进记法

7 表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐近时间复杂度。
渐进表示方法（上界函数） 算法中关键操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作： T(n)=O(f(n)),称为上界函数 渐进符号（O）的定义：当且仅当存在一个正的常数 C和n0 ，使得对所有的 n  n0 ，有 T(n)  Cf(n)，则 T(n) = O(f(n)) 相差一个常数倍数 表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐近时间复杂度。 21:05

8 定义[Big Oh] f(n) = O(g(n)) 当且仅当存在正整数 c 和 n0 ，满足 f(n)  c(g(n)) for all n, nn0 .
F(n)=3n+2, 3n+2<3n+n=4n, f(n)=O(n) 定义[ （n）Omega] f(n) = (g(n))当且仅当存在正整数 c 和 n0 满足，f(n)  c(g(n)) for all n, nn0 . F(n)=3n+2 >3n, f(n)= (n)

9 定义 [(n)Theta] f(n) = (g(n))当且仅当存在正整数 c1 和 c2 ， 以及 n0 ，满足 c1 g(n)  f(n)  c2 g(n) for all n, n n0 ， f(n) = 3n+2 = (n) Little Oh (o) 定义f(n) = o(g(n)) iff f(n) = O(g(n)) and f(n)  (g(n)) f(n) = nlogn, f(n) =o(n2 ), nlogn =O(n2 ), nlogn  (n2 )

10 算法分析中对这些函数的使用 (g): functions that grow at least as fast as g，下界函数,一般用来预估问题求解复杂性。 (g) is the set of functions f, such that f(n)  c g(n) for all n  n0, f(n) = 2n,n2, g(n) = n, O(g): functions that grow no faster as g 上界函数，用来预估算法的性能。 g(n) = n2, f(n) = nlogn, , n, n2, (g): functions that grow at the same rate as g 精确界函数，若设计的算法复杂性为(g)，称该算法为最佳算法。 (g) = O(g)  (g)

11 山东大学计算机科学与技术学院 数据结构 第2章 程序性能
空间复杂性 空间复杂性（Space complexity） 是指运行完一个程序所需要的内存大小。 程序所需要的空间构成 : 指令空间（ Instruction space ） 数据空间（ Data space ） 环境栈空间（ Environment stack space） 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

12 2.2 空间复杂性 指令空间 程序所需要的指令空间的数量取决于如下因素： 把程序编译成机器代码的编译器。 编译时实际采用的编译器选项。
目标计算机。 例子: 计算表达式a+b+b*c+(a+b-c)/(a+b)+4 的代码。 1/31/2020

13 需要存储上述代码 1/31/2020

14 山东大学计算机科学与技术学院 数据结构 第2章 程序性能
空间复杂性组成—数据空间 数据空间 数据空间是指用来存储所有常量和所有变量值所需的空间。 简单变量和常量: 需要的空间取决于所使用的计算机和编译器以及变量与常量的数目。 复合（结构）变量： 包括数据结构所需的空间及动态分配的空间。所需的空间应是每个成员所占用的空间之和。 char 1 float 4 short 2 double int 2 long double 10 long 4 pointer 2 Unit: 字节 图 2-2 Borland C++中简单变量占用空间（p33） 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

15 山东大学计算机科学与技术学院 数据结构 第2章 程序性能
空间复杂性组成—环境栈 环境栈： 环境栈用来保存函数调用返回时恢复运行所需要的信息。 每当一个函数被调用时，下面的数据将被保存在环境栈中： 返回地址。 函数被调用时所有局部变量的值以及传值形式参数的值（仅对于递归函数而言）。 所有引用参数及常量引用参数的定义。 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

16 山东大学计算机科学与技术学院 数据结构 第2章 程序性能
空间复杂性组成小结 S(p)=c+Sp(实例特征 ) c: 固定部分，它独立于实例的特征。 包含指令空间（即代码空间）、简单变量及定长复合变量所占用空间、常量所占用空间等等。 Sp(实例特征 ): 可变部分 实例特征 :这些特征包含决定问题规模的那些因素（如，输入和输出的数量或相关数的大小） 包括：复合变量所需的空间,这些变量的大小依赖于所解决的具体问题;动态分配的空间,这种空间一般都依赖于实例的特征）;递归栈空间（递归函数所需要的栈空间）. 递归栈空间主要依赖于 局部变量及形式参数所需要的空间。 递归的深度（即嵌套递归调用的最大层次）。 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

17 静态数据空间 如矩阵相乘，O(n2 ) 程序所需的空间 输入、输出和中间工作单元 选一个基本的变量存储类型，计算所需的内存变量的渐进函数
和输入尺寸为参数的渐进函数

18 例 程序1-3 T Abc(T a, T b, T c) { return a+b+b*c+(a+b-c)/(a+b)+4; }
例 程序1-3 template<class T> T Abc(T a, T b, T c) { return a+b+b*c+(a+b-c)/(a+b)+4; } 固定部分c :T a,b,c: size of(T) 3* size of(T) (2)动态部分 : 没有申请新的单元 SAbc(实例特征 )=0 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

19 空间复杂性的度量 S(p)= c +Sp c is the static part, declared at program
Sp is the dynamic part, gotten when program runs

20 程序2-1 顺序搜索(Sequenial Search)
template<class T> int SequentialSearch(T a[], const T& x, int n) {//在未排序的数组a[0:n-1]中搜索x，如果找到，则返回所在位置，否则返回- 1 int i; for (i = 0; i < n && a[i] != x; i++); if (i == n) return -1 ; return i; } //T(n) = O(n) 不在的情况 1/31/2020

21 顺序搜索的空间复杂性分析 采用实例特征n 来估算该函数的空间复杂性。 假定T 为int 类型，总的数据空间为12字节 参数a 需要2个字节
实参x需要2个字节， 传值形式参数n 需要2个字节 局部变量i 需要2个字节 每个整型常量0和-1也分别需要2个字节。 因此该空间独立于n，S顺序搜索（n）= 0。 1/31/2020

22 程序1-8 空间复杂性分析 template<class T> T Sum(T a[],int n)
{//计算a[0:n-1]的和 T tsum = 0; for(int i=0;i<n;i++) tsum += a[i]; return tsum; } 实例特征 :n a, n, i, tsum: 空间与n无关 SSum (n) = 0 1/31/2020

23 程序1-9 空间复杂性分析 template<classT> TRsum(T a[],int n)
{//计算a[0:n-1]的和 if(n>0) return Rsum(a,n-1)+a[n-1]; return 0; } 实例特征 :n a(指针), n, 返回地址 2, , 2 (字节) 嵌套调用的层次: Rsum(a, n) Rsum(a, n-1) Rsum(a, n-2)   …… Rsum(a, 1) Rsum(a, 0) S Sum(n)=6(n+1) 1/31/2020

24 阶乘 程序1-7 空间复杂性分析 计算n！的递归函数 int Factorial(int n) {//计算n！
if(n<=1) return 1; return n*Factorial(n-1); } n, 返回地址 2, 2 (字节) 嵌套调用的层次 Factorial(n) Factorial (n-1) Factorial (n-2)   …… Factorial( 1) S Factorial (n)=4*max{n,1} 1/31/2020

25 Time complexity The worst case time complexity
最坏情况下的时间复杂性，即找一个最坏的例子，所需的基本计算步数是多少 The average time complexity 考虑了所以的输入可能性，从统计意义下的平均基本计算步数 从工程或应用角度上看，考虑最坏情况是有意义的，而不能只看最好情况。平均时间复杂性最有意义，但一般计算不出来！

26 最坏情况下的时间复杂性 设 Dn 是所以尺寸为 n 的算法输入集合，设 I 是任意 Dn 中的一个输入，令 t(I) 是算法的基本操作步数，则定义最坏情况的算法时间复杂性函数W(n) W(n) = max{t(I) | I  Dn}

27 期望时间复杂性 令 Pr(I) 为算法选择输入I 的概率，则期望时间复杂性定义为 A(n) = I  Dn Pr(I) t(I).
T(n)A(n)

28 Basic operation(step)
因为在算法中往往有很多不同的操作，如+，-，*，=等，我们一般选最耗时的操作为基本操作 在目前时间复杂性分析中，一般看函数的级别，而忽略前面常数因子 如 n2， 1000n, 前者是O(n2), 后者 O(n)

29 算法时间复杂性分析 理论分析 （非常困难，但被普遍认可） 确定算法的基本计算是什么
基于循环体，递归公式求解，算法的性质分析、利用级数和积分等求解基本计算数量函数f(n)， 找出公认的最坏情况，进行渐进函数的分析 实验比较 (往往不被认可，因为算法的执行时间往往是输入数据的函数） 在testbed 上用 finish time  end time，也常有这样的情况，T(A)>T(B),但对大多数情况，算法A比算法B执行的更快，如快速排序与mergesort.

30 山东大学计算机科学与技术学院 数据结构 第2章 程序性能
常用的渐进符号标记（P61） 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

31 理论分析 1) 对级数可以采用积分的方法求解 2) 多项式采用最高次幂 3）数学手册（如前面的表） 4）根据算法进行结构化分析 ik
定理 2.1 3）数学手册（如前面的表） 4）根据算法进行结构化分析

32 问题按时间复杂性分类 多项式时间算法（容易被计算）
O(1)，常数时间算法，swap(a,b) O(n) 线性算法, sum(list[],n) 指数时间算法，如O(2n ),当n>50,几乎无法计算。NP-hard problems

33 实际测试 利用系统的时钟 在程序开始基本运算前加上语句 在基本运算结束时，加上 Start = clock()
Finish = clock() 实际运行时间= finish-start

34 实际可计算 109 instructions/second
Teraflop computer the 32yr time becomes approx 10 days.

35 109 instructions/second

36 The examples for time complexity analysis
Finding the maximum element Computation for polynormial Matrix multiplication Sorting searching

37 program1-31 寻找最大元素（给出下标）
template<class T> int Max(T a[], int n) {// 寻找a [0 : n-1]中的最大元素 int pos = 0; for (int i = 1; i < n; i++) if (a[pos] < a[i]) pos = i; return pos; } 每次调用Max(a,n)需要执行n-1次比较。 1/31/2020

38 1.2.6 递归加和 程序 1-9 template<class T> T Rsum(T a[], int n) {
if (n > 0) return Rsum(a, n-1) + a[n-1]; return 0; } 1/31/2020

39 递归程序分析 在分析一个递归程序的执行步数时，通常可以得到一个计算执行步数的递归等式(如tRsum(n)=2+tRsum(n-1)，n>0且tRsum(2)=0)。 这种递归公式被称为递归等式(recurrence equation) 。 可以采用重复迭代的方法来计算递归等式，如:tRsum(n)=2+tRsum(n-1)=2+2+tRsum(n-2)=4 +tRsum(n-2)...=2n+tRsum(0)=2(n+1) 其中n≥0，因此函数Rsum的执行步数为2(n+1)。 1/31/2020

40 多项式求值 1/31/2020

41 程序2-3多项式求值算法 template <class T>
T PolyEval(T coeff[], int n, const T& x) { / /计算n次多项式的值，coeff[0:n]为多项式的系数 T y=1, value= coeff[0] ; for ( int i = 1; i <= n; i++) { //累加下一项 y *= x; value += y * coeff[i] ; } return value; 1/31/2020

42 多项式求值算法时间复杂性 使用维数n 作为实例特征。 假定根据for循环内部所执行的加和乘的次数来估算时间复杂性。
进入for循环的总次数为n，每次循环执行1次加法和2次乘法（这种操作计数不包含循环控制变量i 每次递增所执行的加法）。 加法的次数为n，乘法的次数为2n。 1/31/2020

43 多项式求值优化 Horner 法则采用如下的分解式计算一个多项式：
P(x)=(…(cn*x+cn-1)*x+cn-2)*x+cn-3)*x+…)*x+c0 p(x)=2x4－x3＋3x2＋x－5 =x(x(x(2x－1)＋3)＋1)－5 系数 c4 c3 c2 c1 c0 2 －1 3 1 －5 x=3 3*2－1=5 3*5+3=18 3*18+1=55 3*55－5=160 1/31/2020

44 程序2-4 利用Horner 法则对多项式进行求值
template <class T> T Horner(T coeff[], int n, const T& x) { //计算n次多项式的值，coeff[0 : n]为多项式的系数 T value= coeff [n] ; for( int i = 1; i <= n; i++) value = value * x + coeff[n-i] ; return value; } 1/31/2020

45 比较 可以估算出该程序的时间复杂性为n 次加法和n 次乘法。
由于函数PolyEval 所执行的加法次数与Horner 相同，而乘法次数是Horner的两倍，因此，函数 Horner 应该更快。乘法运算往往是加法运算的4倍以上时间。 1/31/2020

46 时间复杂性函数的计算 理论分析 定义一个基本运算，寻找到算法运行基本操作最多的输入实例，通过数学的方法给出其上下界函数（不等式放大） 实际测试 建立一个测试数据集合，实际多次抽样测试算法的实际运行时间（竞赛的方法），选出最好的算法。

47 程序2-1 顺序搜索(Sequenial Search)
template<class T> int SequentialSearch(T a[], const T& x, int n) {//在未排序的数组a[0:n-1]中搜索x，如果找到，则返回所在位置，否则返回- 1 int i; for (i = 0; i < n && a[i] != x; i++); if (i == n) return -1 ; return i; } 1/31/2020

48 程序2-1 顺序搜索性能分析 假定每个元素被查找的概率是相同的，成功查找情况下 最好情况， 比较1次
最好情况， 比较1次 最坏情况， 比较n次 （T(n)= O(n)） 在位置i找到比较步数 i 平均情况， 1/31/2020

49 c[i][j]=c[i][j]+a[i][k]*b[k][j]; }
例1：N×N矩阵相乘 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; } 算法中的基本操作 * c[i][j]=c[i][j]+a[i][k]*b[k][j]; 21:05

50 山东大学计算机科学与技术学院 数据结构 第2章 程序性能
例2-5 计算名次 元素在队列中的名次（rank）可定义为队列中所有比它小的元素数目加上在它左边出现的与它相同的元素数目。 例如，给定一个数组a=[4, 3, 9, 3, 7]作为队列，则各元素的名次为r =[2, 0, 4, 1, 3]。 //算法思想：对处于位置i的元素，计算位于1-(i-1)位置上比自己小的元素个数。同时也对这些元素的rank贡献。 template <class T> void Rank(T a[], int n, int r[]) { for ( int i=0; i < n; i++) r[i]=0; for ( int i=1; i < n; i++) for ( int j=0; j < i; j++) if (a [j]≤a[ i]) r[ i] + + ; else r[j] + + ; } 比较次数 : …+n-1 =(n-1)*n/2 = O(n2 ) 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

51 排序算法 对给定的无序对象序列和一个全序关系>, 输出一个按升序（降序）的新序列。 我们可以利用名次计算得到排序

52 void rearrange(T a[], int n, int r[])
利用前面的名次计算，直接赋值 template <class T> void rearrange(T a[], int n, int r[]) { T *u = new T [n] //申请一个一维数组 for ( int i=0; i < n; i++) u[r[i]] = a[i] ; for ( int i=1; i < n; i++) a[i] = u[i]; delete [] u; } 因为需要事先计算 r, 故时间复杂性为O(n2)

53 其他排序 插入排序 冒泡排序 快速排序

54 向一个有序数组中插入元素 template <class T> void Insert(T a[], int& n， const T&x) int i; // suppose the size of array a > n, where n is the current number of elements in a; { for ( int i=n-1; i>=0 && x < a[i]; i-- ) a[j+1] = a[i] ; //从右向左寻遍历，只要大于x，则向后搬动 a[j+1]=x; // j+1是x放入的位置 n++// add a new element } } 基本操作比较，最好T(n) = 1；最差n

55 时间复杂性分析

56 插入排序 思想：初始假定已排序数组长度为1，只有a[0].然后从目前序列的最后面j向前看，只要比 t大，把A的元素向后移动一位，直到a[j] <t,把t插入位置j+1。 程序：//a[0,n-1] template <class T> void InsertionSort(T a[], int n) { for ( int i=1; i<n; i++ ) { T t=a[i]; int j; for ( j=i-1; j>=0 && t<a[j]; j-- ) a[j+1] = a[i] ; a[j+1]=t; } 2020/1/31

57 最坏情况 找个特例，即原来是降序序列，改为增序序列
分析： 最好情况 比较 n-1次，移动0次 最坏情况 找个特例，即原来是降序序列，改为增序序列 移动次数 1+2+…+n-1=n*(n-1)/2次，移动也是n*(n-1)/2次 2020/1/31

58 之五：冒泡排序 思想：从下向上，把“轻”的元素上浮。自下(a[0])而上(a[n-1])依次两两比较，发现逆序即进行交换直至a[n-1]，下一次再从a[0]至a[n-2]做如上处理，如此进行n-1遍或当某遍未发生交换即可结束。 程序： template <class T> void Bubble(T a[], int n) //一次冒泡 { for ( int i=0; i<n-1; i++ ) if ( a[i]>a[i+1]) Swap(a[i],a[i+1]); //一定把最大元素放到n-1的位置 } template <class T> // 截至到位置i的冒泡 void BubbleSort(T a[], int n) { for ( int i=n; i>1; i-- ) Bubble(a, i); //从位置i 开始冒泡 2020/1/31

59 之五：只要没有逆序终止的冒泡排序 程序： template <class T>
bool bubble(T a[], int n) //一次冒泡 bool swapped = false { for ( int i=0; i<n-1; i++ ) if ( a[i]>a[i+1]) {Swap(a[i],a[i+1]); swapped = true; } template <class T> // 截至到位置i的冒泡 void BubbleSort(T a[], int n) { for ( int i=n; i>1 && bubble(a, i); i--); //从位置i 开始冒泡 2020/1/31

60 最坏情况 比较 (n-1)+(n-2)+…+1=n*(n-1)/2次，交换也是n*(n-1)/2次
分析： 最好情况 比较 n-1次，交换0次 最坏情况 比较 (n-1)+(n-2)+…+1=n*(n-1)/2次，交换也是n*(n-1)/2次 本章介绍的几种排序方法的时间复杂性都是O(n*n)的，后面还会陆续介绍性能更好的方法 2020/1/31

61 奇偶排序

62 快速排序Quicksort Input: A set of numbers S.
Output: The elements of S sorted in increasing order. 1.若 |S| < 3 直接比较排序；返回 2选S中最左元素作为pivot元素y. 3.分割S为S1,S2, S1={x|x<y}; S2={x|x>y}. 4.递归调用RandQS对S1,S2排序； 5 输出RandQS(S1); y; RandQS(S2);

63 把S分为S1,S2的过程。 左找大，右找小，右放vac, 左放刚空出的右元素, 当l>r, vac为pivot的 位置. 45 45

64 QuickSort 最坏时间复杂性O(n2 )—已经排序序列 期望时间复杂性O(nlogn),比其他排序算法节省一半以上的时间。

65 山东大学计算机科学与技术学院 数据结构 第14章 分而治之算法
快速排序实现 template<class T> void QuickSort(T*a, int n) {// 对a[0:n-1] 进行快速排序; 要求a[n] 必须有最大关键值 quickSort(a, 0, n-1); void quickSort(T a[], int l, int r) {//排序a[l:r]，a[r+1]有大关键值 if (l>=r) return; int i=l, // 从左至右的游标 j=r+1; // 从右到左的游标 T pivot=a[l]; 山东大学计算机科学与技术学院 数据结构 第14章 分而治之算法 65

66 山东大学计算机科学与技术学院 数据结构 第14章 分而治之算法
// 把左侧>= pivot的元素与右侧<= pivot 的元素进行交换 while (true) { do {// 在左侧寻找>= pivot 的元素 i=i+1; } while (a[i]< pivot); do {// 在右侧寻找<= pivot 的元素 j=j-1; } while (a[j]>pivot); if (i>=j) break; // 未发现交换对象 Swap(a[i], a[j]); } //设置pivot a[l]=a[j]; a[j] = pivot; quickSort(a, l, j-1); // 对左段排序 quickSort(a, j+1, r); // 对右段排序 山东大学计算机科学与技术学院 数据结构 第14章 分而治之算法 66

67 两种搜索（查找）算法介绍 顺序搜索 性能： 不成功查找比较次数=n-1;
template <class T> int SequentialSearch(T a[], const T &x, int n) { int i; for ( i=0; i<n && a[i]!=x; i++ ) //数组下标从0~(n-1) if ( i==n) return -1; return i; } 性能： 不成功查找比较次数=n-1; 成功查找比较次数=1*p0,+2*p1,+…+n*pn-1，其中pi为第i 个元素被查找的概率； 一般认为pi均等，为1/n，则=(1+n)/2 2020/1/31

68 折半搜索//前提序列是有序的（增或减） 思想：对给定的表a[0..n] 和将被搜索元素x，首先将x与a中间元素a[n/2]比较，相等则返回;否则，若x比中间元素小,则只在a[0..n/2-1]继续搜索;否则在a[n/2+1,n-1]继续搜索。 2020/1/31

69 template <class T> int BinarySearch(T a[], const T &x, int n)
{ int left=0; int right=n-1; while (left<=right) { int middle=(left+right)/2; // int 强制把商变成整数 if ( x==a[middle]) return middle; //找到 if ( x>a[middle]) left=middle+1; // 确定下一步从左右哪半块继续找 else right=middle-1; } return -1; 性能： 最好情况一次比较成功； 最多经过┌log n ┐次比较即可得出结论; 2020/1/31

70 山东大学计算机科学与技术学院 数据结构 第2章 程序性能
复杂性函数的取值变化 logn n nlogn n2 n3 2n 1 2 3 4 5 8 16 32 24 64 160 256 1024 512 4096 32768 65536 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

71 山东大学计算机科学与技术学院 数据结构 第2章 程序性能
实际复杂性 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

72 考虑到数组下标解析和缓存的影响 程序 2-22 template<class T> void squreMatrixMultiply(T **a,T **b,T **c, int n) { for (int i = 0; i<n; i++) for (int j = 0; j<n; j++) { T sum = 0; for (int k = 0; k< n; k++) sum += a[i][k]*b{k][j]; c[[i][j] = sum; } } 需要注意下标解析费时，尽量对连续存放数据进行操作

73 template<class T> void squreMatrixMultiply1(T. a,T. b,T
template<class T> void squreMatrixMultiply1(T **a,T **b,T **c, int n) { for (int i = 0; i<n; i++) for (int j = 0; j<n; j++) c[i][j] = 0; for (int i = 0; i<n; i++) for (int j = 0; j<n; j++) for (int k = 0; k< n; k++) c[i][j] += a[i][k]*b[k][j]; }

74 template<class T> void fastSqureMatrixMultiply(T. a,T. b,T
template<class T> void fastSqureMatrixMultiply(T **a,T **b,T **c, int n) { for (int i = 0; i<n; i++) for (int j = 0; j< n; j++) c[i][j] = 0; for (int i = 0; i<n; i++) for (int k = 0; k<n; k++) for (int j = 0; j< n; j++) c[i][j] += a[i][k]*b[k][j]; }

75 单位： 秒

76 练习 P59, 11,13,16,17 P60 26 P63 36