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))