设n为正整数,利用大o记号将下列程序段的执行时间表示为n的函数（1）i＝1""-k=100.while（i＜n）k＝k＋1i＝i＋10（2）i＝1j＝0while（i＋j＜＝n）if（i＞j）j＋＋elsei＋＋（3

Question

设n为正整数,利用大o记号将下列程序段的执行时间表示为n的函数
　　（1）i＝1""-k=100.while（i＜n）　k＝k＋1　i＝i＋10　（2）i＝1　j＝0　while（i＋j＜＝n）　if（i＞j）j＋＋　else　i＋＋　（3）for　（i＝1,i＜=n --1,i ++ k） k =i for(j =i +1,jr [j +1]) k =j t =R [k] R[K ]=R [I],R [i]=t .

Answer 1

(1) i=1; k=0
while(i { k=k+10*i;i++;
} ◆ T(n)=n-1
∴ T(n)=O(n)
◇ 这个函数是按线性阶递增的
(2) i=0; k=0;
do{
k=k+10*i; i++;
}
while(i ◆ T(n)=n
∴ T(n)=O(n)
◇ 这也是线性阶递增的
(3) i=1; j=0;
while(i+j1
while (x>=(y+1)*(y+1))
y++; ◆ T(n)=n1/2
∴ T(n)=O(n1/2)
◇ 最坏的情况是y=0,那么循环的次数是n1/2次,这是一个按平方根阶递增的函数.
(5) x=91; y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
else x++; ◆ T(n)=O(1)
◇ 这个程序看起来有点吓人,总共循环运行了1000次,但是我们看到n没有? 没.这段程序的运行是和n无关的,就算它再循环一万年,我们也不管他,只是一个常数阶的函数.