例1.9void matrixadd(int]] A,int[l[] B,int[][] C,int n)1/语旬①for（inti=o;i<n;i++)1/语句②for(intj=o;j<n;j++)1/语句③C[i][j]=A[i][j]+B[i][j]T(n)=2n2+2n+1=0(n2)11/56
例1.9 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)=2n 2+2n+1=O(n 2) 11/56
一般地：一个没有循环的算法的执行时间与问题规模n无关，记作0（1），也称作常数阶一个只有一重循环的算法的执行时间与问题规模n的增长呈线性增大关系，记作o(n)，也称线性阶。其余常用的算法时间复杂度还有平方阶o(n2)、立方阶0(n3)、对数阶o(1ogzn)指数阶0(2n）等。12/56
一个没有循环的算法的执行时间与问题规模n无关，记作O(1)，也称作常数阶。 一个只有一重循环的算法的执行时间与问题规模n的增长呈线性增大关系，记作 O(n)，也称线性阶。 其余常用的算法时间复杂度还有平方阶O(n 2)、立方阶O(n 3)、对数阶O(log2n)、 指数阶O(2 n)等。 一般地： 12/56
各种不同算法时间复杂度的比较关系如下：0(1)<0(1og2n)<0(n)<0(n1og2n)<0(n2)<0(n3)<0(2n)<0(n!)多项式阶：指数阶：P问题NP问题NP=P？是目前计算机科学的难题之一13/56
各种不同算法时间复杂度的比较关系如下： O(1)<O(log2n)<O(n)<O(nlog2n)<O(n 2)<O(n 3)<O(2 n)<O(n!) 指数阶： NP问题 多项式阶： P问题 NP = P？是目前计算机科 学的难题之一 13/56
int Sumi(int n)int Sum2(int n)f int i,s=o;( int s;for（i=l;i<=n;i++)s=n*(n+1)/2;s+=i;return s;return s;20(1)o(n)Sum2更好14/56
int Sum1(int n) { int i,s=0; for (i=1;i<=n;i++) s+=i; return s; } int Sum2(int n) { int s; s=n*(n+1)/2; return s; } O(n) O(1) Sum2更好 14/56
3）简化的算法时间复杂度分析一种简化的算法时间复杂度分析方法是，仅仅考虑算法中的基本操作。所谓基本操作是指算法中最深层循环内的原操作。而算法执行时间大致等于基本操作所需的时间×其运算次数。所以在算法分析时，计算T(n)时仅仅考虑基本操作的执行次数。15/56
3）简化的算法时间复杂度分析 一种简化的算法时间复杂度分析方法是，仅仅考虑算法中的基本操作。 所谓基本操作是指算法中最深层循环内的原操作。而算法执行时间大 致等于基本操作所需的时间×其运算次数。所以在算法分析时，计算 T(n)时仅仅考虑基本操作的执行次数。 15/56