求下列程序段的时间复杂度,1.for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x+=delta;2.i=1;j=0;while(i+j<=n)if(i>j)j++;elsei++;

Question

求下列程序段的 时间复杂度,
1.
for ( i = 1 ; i < = n ; i++ )
for ( j = 1 ; j < = i ; j++ )
for ( k = 1; k < = j ; k++ )
x+=delta;
2.
i = 1;
j = 0;
while ( i + j < = n )
if ( i > j )
j++;
else
i++;

Answer 1

1.
先观察 for ( j = 1 ; j < = i ; j++ )
for ( k = 1; k < = j ; k++ )
可知若i=w,则程序段执行次数为1+2+..+w.
因此定义f(i)=1+2+..+i
那么总的执行次数为
f(1)+f(2)+..+f(n)=1*n+2*(n-1)+3*(n-2)+..+(n-1)*2+n=n^2*(1+n)/2-1*2-2*3-3*4-...-(n-1)*n
不好意思水平有限,只能到这步了,应该是小于n^3的.
2.我们可以发现,每次进while,无论如何i+j会变大一,所以while语句会执行n次
时间复杂度 o(n)