| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1760 人关注过本帖
标题:一个简单的求时间复杂度的题目
取消只看楼主 加入收藏
qq383264679
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:155
专家分:130
注 册:2012-1-19
结帖率:88.89%
收藏
已结贴  问题点数:20 回复次数:2 
一个简单的求时间复杂度的题目
可能对与一个双重循环的这个样一个问题,我就不会再这里发帖了。例子如下:
          for(i = 0; i < n; i++)
               for(j = 0; j < i; j++)
                         { a++;  }
    基本语句c1:a++;
       这个题目用数学归纳法很好证明:
当i = 0; f(n) = 0;
当i = 1; f(n) = 1;
当i = 2; f(n) = 2;
....
当i = n-1; f(n) = n-1;
  基本语句执行的次数便是:0 + 1 + 2 + ....+ (n-1) = n(n-1)/2;
    f(n) = n*(n-1)/2 < n*n/2 = O(n~2);
但是对与一个一个三重循环
           for(i = 0; i < n; i++)
               for(j = 0; j < i; j++)
                   for(k = 0; k < j; k++
                         { a++;  }
却不知道怎么分析,希望高手讲解!


搜索更多相关主题的帖子: 数学归纳法 
2012-09-03 19:00
qq383264679
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:155
专家分:130
注 册:2012-1-19
收藏
得分:0 

  大侠们 也是硬算的么?好吧 ,我下去同理可得,要算一页纸的哦
2012-09-04 06:53
qq383264679
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:155
专家分:130
注 册:2012-1-19
收藏
得分:0 
结贴:
  附上本人的答案循环次数:(n~3 - 3 * n~2 + 2 * n) /6
2012-09-04 18:32
快速回复:一个简单的求时间复杂度的题目
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.028693 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved