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！）。
热门推荐
10 新年门口花束祝福语简短
11 盘锦结婚祝福语大全简短
12 父母生日祝福语 简短独特
13 家庭恩爱祝福语简短英文
14 高考俄语祝福语大全简短
15 虎年祝福语 诗句唯美简短
16 生日婚礼祝福语简短精辟
17 虎年喝酒拜年祝福语简短
18 教师闺蜜祝福语简短