题目
试分析下面各程序段[1]的时间复杂度。(1)x=90; y=100; while(y>0)if(x>100)(x=x-10;y--;)else x++;
试分析下面各程序段[1]的时间复杂度。(1)x=90; y=100; while(y>0)if(x>100){x=x-10;y--;}else x++;
题目解答
答案
答案:O(1)解释:程序的执行次数为常数阶。[算法描述]void Arrange(int A[],int n)//n个整数存于数组A中,本算法将数组中所有正数排在所有负数的前面{int i=0,j=n-1,x; //用类C编写,数组下标从0开始while(i{while(i0) i++;while(iif(i}// while(i}//算法Arrange结束.[算法讨论]对数组中元素各比较一次,比较次数为n。最佳情况(已排好,正数在前,负数在后)不发生交换,最差情况(负数均在正数前面)发生n/2次交换。用类c编写,数组界偶是0..n-1。空间复杂度为O(1).
解析
步骤 1：分析循环条件
程序中有一个while循环，其条件是y>0。初始时y=100，每次循环中y的值减1，因此循环将执行100次。
步骤 2：分析循环体内的条件判断
在循环体内，有一个if条件判断，判断x是否大于100。初始时x=90，每次循环中x的值加1，直到x=100。当x=100时，条件判断将变为x>100，此时x的值将减10，y的值减1。因此，当x=100时，循环将执行10次，每次x的值减10，y的值减1，直到x<100。
步骤 3：计算总执行次数
在x=90到x=100的范围内，循环将执行100次。在x=100到x<100的范围内，循环将执行10次。因此，总执行次数为100+10=110次。
程序中有一个while循环，其条件是y>0。初始时y=100，每次循环中y的值减1，因此循环将执行100次。
步骤 2：分析循环体内的条件判断
在循环体内，有一个if条件判断，判断x是否大于100。初始时x=90，每次循环中x的值加1，直到x=100。当x=100时，条件判断将变为x>100，此时x的值将减10，y的值减1。因此，当x=100时，循环将执行10次，每次x的值减10，y的值减1，直到x<100。
步骤 3：计算总执行次数
在x=90到x=100的范围内，循环将执行100次。在x=100到x<100的范围内，循环将执行10次。因此，总执行次数为100+10=110次。