例1.8void matrixadd(int[][] A,int[][] B,int[][] C,int n)1/语句①{for(int i=o;i<n;i++)1语句②for (int j=o;j<n;j++)1/语句③C[i][j]=A[][j]+B[i][];基本操作，执行次数为n2T(n)=n2=0(n2)16/56
基本操作，执行次数为n 2 例1.8 void matrixadd(int[][] A,int[][] B,int[][] C,int n) { for (int i=0;i<n;i++) //语句① for (int j=0;j<n;j++) //语句② C[i][j]=A[i][j]+B[i][j]; //语句③ } T(n)=n 2=O(n 2) 16/56
【例1.9】分析以下算法的时间复杂度。void fun(int n)(int s=o;for (int i=o;i<=n;i++)for(int j=o;j<=i;j++)for (int k=;k<j;k++)s++;K基本操作return s;1-172n算法频度为：1-G-1-0+1)=)ZZT(n) =i=0i=0k=0i=0j=0i=0=02nn2n3+6n2+ 4ni(i+ 1)127i2= 0(n3)22121=0i=0i=017/56
【例1.9】分析以下算法的时间复杂度。 void fun(int n) { int s=0; for (int i=0;i<=n;i++) for (int j=0;j<=i;j++) for (int k=0;k<j;k++) s++; return s; } 基本操作 算法频度为： 17/56
算法的最好、最坏和平均时间复杂度2设一个算法的输入规模为n，D是所有输入的集合，任一输入IEDn，P(I)是I2P(I)=1 ，T(I)是算法在输入I下的执行时间，则算法的平均时出现的概率，有TeDn间复杂度为：ZP(I)×T(I)A(n) =TeDn18/56
设一个算法的输入规模为n，Dn是所有输入的集合，任一输入I∈Dn，P(I)是I 出现的概率，有 ，T(I)是算法在输入I下的执行时间，则算法的平均时 间复杂度为： = Dn I A(n) P(I) T(I) = Dn I P(I) 1 2. 算法的最好、最坏和平均时间复杂度 18/56
例如，10个1～10的整数序列递增排序：n=10I={1, 2, 3, 4,5, 6,7, 8, 9, 10]I2={2, 1, 3, 4, 5,6, 7, 8, 9, 10)构成Dn，P(I)=1/mIm=(10,9,8,7,5,4,3,2,1)6.所有可能的初始序列有m个，m=10！19/56
例如，10个1～10的整数序列递增排序： n=10 I1={1，2，3，4，5，6，7，8，9，10} I2={2，1，3，4，5，6，7，8，9，10} . Im={10，9，8，7，6，5，4，3，2，1} 构成Dn，P(I)=1/m 所有可能的初始序列有m个，m=10! 19/56