C ++中时间复杂度分析的实践问题
任何算法的时间复杂度是该算法完成所需的时间。它是显示算法效率和进行比较分析的重要矩阵。我们倾向于降低算法的时间复杂度,使其更加有效。
查找以下代码段的时间复杂度
for(i= n ; i > 0; i++){
cout<<i;
i++;
}该循环的最大值为n,但是i在for循环中将增加两次,这将使时间花费一半。
时间复杂度:O(n/2)
for(i= n ; i > 0; i++){
for(j = 0; j<n;j++){
cout<<i;
}
}在这里可以证明,对于外循环的每个迭代,内循环将执行n次。
因此,时间复杂度:O(n2)或O(N*N)
int i = N;
while(i){
cout<<i;
i = i/2 ;
}此处,i的每次迭代值都将除以2。因此,时间复杂度:O(log(n))
if(i > j ){
j>23 ? cout<<j : cout<<i;
}代码中有两个条件语句。每个条件语句的时间复杂度=O(1)。
时间复杂度:O(2)
for(i= n ; i > 0; i++){
for(j = 0; j<n;j*2){
cout<<i;
}
}在这里,我们有嵌套循环,而内部循环有乘法作为增量运算符。因此,内部循环的复杂度将为log(n)。并且具有外部将为n阶。所以,
时间复杂度:O(nlog(n))