C ++中一个有趣的时间复杂度问题
时间复杂度可以定义为算法运行其平均情况所需的时间。
让我们看看并计算一些基本功能的时间复杂度。
方法
void counter(int n){
for(int i = 0 ; i < n ; i++){
for(int j = 1 ; j<n ; j += i ){
cout<<i<<” ”<<j;
}
cout<<endl;
}
}上面的方法将对所有值n/I次运行，即第一次迭代为n次，最后一次迭代为1次。
据此，总时间复杂度为
(n/1 + n/2 + n/3 + …. + n/n) = n (1/1 + ½ + ⅓ + …. 1/n)
现在（1/1+½+⅓+…。1/n）的值等于O（logn）。
该代码的时间复杂度为O(nlogn)。
方法
void counter(n){
int i , j ;
for(int i = 1 ; i <= n ; i++){
for(j = 1; j <= log(i) ; j++){
cout<<i<<” ”<<j;
}
}
}该函数的总复杂度为O（log1）+O（log2）+O（log3）+…。+O（logn），即O（logn！）。