20道与时间复杂度相关的题_时间复杂度习题

// (1)
x = 90; y = 100;
while(y > 0){
    if(x > 100){
        x = x - 10;
        y--;
    }else{
        x++;
    }
}

(1)   语句x++每循环执行11次，y--就会执行1次。当y--执行100次时，程序运行结束。故基本操作的语句频度为11 * 100 = 1100，时间复杂度为O(1)，常数阶。

//（2）
for (i = 0; i < n; i++)
      for (j = 0; j < m; j++)
         a[i][j] = 0;

(2)  外循环执行n次，内循环执行m次，基本操作a[i][j] = 0执行总数为m * n，时间复杂度为O(m * n)。

// （3）
s = 0;
for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
         s += B[i][j];
sum = s;

(3)  s += B[i][j]执行次数为n * n，时间复杂度为O(n * n)。

//（4）
i = 1;
while(i <= n)
    i = i*3;

(4)  设语句频度为x，则 i * (3 ^ x) > n。因 i = 1，故 x > log3(n)，时间复杂度为O(log3(n))。

//（5）
x = 2;
while(x < n/2)
    x = x * 2;

(5)  思路同上，时间复杂度为O(log2(n))。

//（6）
x = 0;
for(i = 1; i < n; i++)
    for (j = 1; j <= n-i; j++)
        x++;

(6)  外循环共执行 n-1 次，内循环依次执行 n-1，n-2...1次，语句频度为 n*(n-1)/2，时间复杂度为O(n^2)。

//（7）
x = 0;
for(k = 1; k <= n; k*=2)
    for (j = 1; j <= n; j++)
        x++;

(7)  外层循环执行 log2(n) 次，内循环执行 n 次，总次数为 n*log2(n) 次。时间复杂度为O(n*log2(n))。

//（8）
int fact(int n){
    if(n <= 1)
        return 1;
    return n*fact(n-1);
}

(8)  每次执行函数，都会递归调用一次，同时参数减一。故总时间复杂度为 O(n)。

//（9）
x = n;     //n>1
y = 0;
while(x ≥ (y+1) * (y+1))
    y++;

(9)  设循环次数为 k，n 与 k 应满足 k^2 > n，即 k > n^(1/2)。时间复杂度为O(n^(1/2))。

//（10）
int func(int n){
    int i = 0, sum = 0;
    while(sum < n)
        sum += ++i;
    return i;
}

(10)  设循环次数为 k，n 与 k 应满足 k*(k+1)/2 > n，即 k > (2*n)^(1/2)。时间复杂度为O((2*n)^(1/2))。

//（11）
for(int i= n-1; i > 0; i--)
	for (int j = 0; j < i; j++) 
		if(A[j] > A[j+1])
			A[j]与A[j+1]对换;

(11)  最好情况下，程序时间复杂度为常数阶。在最坏情况下，外层循环 n-1 次，内层循环为 n-2,n-3...1,0 次，故语句频度为 (n-1)*(n-2)/2 次，时间复杂度为 O(n^2)。

// (12)
void fun4(int N) {
	int count = 0; 
	for (int k = 0; k < 100; k++) {
		++count;
	}
	printf("%d\n", count);
}
 

(12)  ++count 频度为100，时间复杂度为 O(1)，常数阶。

// (13)
for(int i=0;i<n;i++){
 
   System.out.println(result[i]);  //执行一次
 
}

(13)  语句频度为 n 次，时间复杂度为 O(n)，线性阶。

// (14)
 
int result=1;
 
while(result<n){
 
    result=result*2; //时间复杂度为O(1)
 
}

(14)  时间复杂度为 O(log2n)，对数阶。

// (15)
 
//二分查找法
int BinarySearch(int* a, int  n, int x) {
	assert(a);
	int begin = 0;
	int end = n - 1;
	
	while (begin < end) {
	
		int mid = ((end - begin) >> 1) + begin; //计算end与begin的中间值，右移1位相当于除以2
		
		if (a[mid] < x) {begin = mid - 1;}
		else if(a[mid]>x){end = mid;}
		else {return mid;}
		
	}
	
	return -1;
}

(15)  最坏情况下，时间复杂度为 O(log2n)。

// (15)
void fun(int n){
    int i=0;
    while(i*i*i<=n){
        i++;
    }
}

(16)  时间复杂度为 O(n^(1/3)) 

// (16)
// 多个复杂度组合
 
for(int i=0;i<n;i++){   
   for(int j=0;j<n;i++){ 
       System.out.println(result[i][j]);  //执行一次 
   } 
}
 
for(int i=0;i<n;i++){  
   System.out.println(result[i]);  //执行一次 
}
 

(17)  两个循环执行次数共为 n^2 + n 次，时间复杂度为 O(n^2)。

// (17)
// 多个复杂度组合
if(flag){ 
   for(int i=0;i<n;i++){  
       for(int j=0;j<n;i++){ 
          System.out.println(result[i][j]);  //执行一次 
       } 
    } 
}else{ 
    for(int i=0;i<n;i++){   
       System.out.println(result[i]);  //执行一次 
    } 
}

(17)  两个循环时间复杂度分别为 O(n^2) 和 O(n)，按最坏情况考虑，时间复杂度应为 O(n^2)。

// (18)
void fun(int n){
    int i,k;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            k=1;
            while(k<=n){
                k = 5*k;
            }
        }
    }
}
 

(18)  for循环总次数为 n^2，while循环总次数为 log5n，时间复杂度为 O(n^2 * log5n)。

// (19)
//求阶乘
long long Factorial(int N) {
	return N < 2 ? N : N * Factorial(N - 1) ;
}
 

(19)  时间复杂度为 O(n)。

// (20)
int m=0, i, j;
for(i=l;i<=n;i++)
   for(j=1;j<=2 * i;j++)
      m++;

(20)  m++执行次数为 n*(n+1)，时间复杂度应为 O(n^2)。