例1:求下面程序的时间复杂度。 程序段一 该程序中“x增1”是基本 数据结构 for(=1;j<=n;++j) 操作语句,其频度为n2,其 for(k=1;k<=n;++k){ 时间复杂度为0(m2),为平方 ++X: S+x 程序段二 该程序中“x增1”是基本 操作语句,其频度为1,其 时间复杂度为O(1),为常量 阶。 程序段三 该程序中“x增1”是基本 l;i<=n;++i){ 操作语句,其频度为n,其 时间复杂度为om),为线性 阶 分课 Exoiint I,j, t 析堂 数(1)for(=1;I10;I++) 程作 结(2)prin(“n%d”,I); 构 序业 (3)for(I=1;I<=2;I+) printf(“n”) (5)mr(=1;k=9;I+) 论(6)for(j=1;j<=I;j+) (7){t=I*j; printf((“%5d”,t);} 28 (8)for(j=1;j3;j++) 中各语句的频度 (9) printi“m”);}14 数 据 结 构 之 绪 论 27 程序段一： for(j=1;j<=n;++j) for(k=1;k<=n;++k){ ++x; s+=x; } 程序段二： { ++x; s=0; } 程序段三： for(i=1;i<=n;++i) { ++x; s+=x; } 例1：求下面程序的时间复杂度。 该程序中“x增1”是基本 操作语句，其频度为n2，其 时间复杂度为O(n2)，为平方 阶。 该程序中“x增1”是基本 操作语句，其频度为1，其 时间复杂度为O(1)，为常量 阶。 该程序中“x增1”是基本 操作语句，其频度为n，其 时间复杂度为O(n)，为线性 阶。 数 据 结 构 之 绪 论 28 课 堂 作 业 分 析 程 序 中 各 语 句 的 频 度 Ex( ) { int I , j , t ; (1) for( I=1 ; I<10 ; I++) (2) printf(“\n %d” , I ); (3) for(I=1; I<=2; I++) (4) printf(“\n”); (5) for(I=1; I<=9; I++){ (6) for(j=1; j <= I ; j++) (7) { t = I * j ; printf(“%5d”,t); } (8) for(j=1; j<3 ; j++) (9) printf(“\n”); } }