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, j<=n,j ++ ) if (r｛j ｝>r [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+j<=n)
{
if (i else i++;
} ◆ T(n)=n/2
∴ T(n)=O(n)
◇ 虽然时间函数是n/2,但其数量级仍是按线性阶递增的。
(4)x=n; // n>1
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无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。