C++时间复杂度分析练习题

任何算法的**时间复杂度**是指算法完成所需的时间。它是衡量算法效率和进行比较分析的重要指标。我们倾向于降低算法的时间复杂度，使其更有效。

示例1

找出以下代码片段的时间复杂度

for(i= 0 ; i < n; i++){
   cout<< i << " " ;
   i++;
}

循环的最大值为n，但i在for循环中将被递增两次，这将使时间减半。因此，时间复杂度为O(n/2)，相当于O(n)。

示例2

找出以下代码片段的时间复杂度

for(i= 0 ; i < n; i++){
   for(j = 0; j<n ;j++){
      cout<< i << " ";
   }
}

内循环和外循环都执行n次。因此，对于i的单个值，j循环n次，对于n个i值，j将总共循环n*n = n²次。因此，时间复杂度为O(n²) 。

示例3

找出以下代码片段的时间复杂度

int i = n;
while(i){
   cout << i << " ";
   i = i/2;
}

在这种情况下，每次迭代后，i的值都变为其先前值的一半。因此，序列将类似于：。因此，时间复杂度为O(log n)。

示例4

找出以下代码片段的时间复杂度

if(i > j ){
   j>23 ? cout<<j : cout<<i;
}

代码中包含两个条件语句。每个条件语句的时间复杂度为O(1)，对于其中的两个，它为O(2)，相当于O(1)，即**常数**。

示例5

找出以下代码片段的时间复杂度

for(i= 0; i < n; i++){
   for(j = 1; j < n; j = j*2){
      cout << i << " ";
   }
}

内循环执行(log n)次，而外循环执行n次。因此，对于i的单个值，j执行(log n)次，对于n个i值，j将总共循环n*(log n) = (n log n)次。因此，时间复杂度为O(n log n)。

Sudhir Sharma

更新于：2021年8月2日

9K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习