| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
买学问 - 大牛一对一辅导,有问必答买学问 - 专业的付费知识问答平台
共有 692 人关注过本帖
标题:求时间复杂度
只看楼主 加入收藏
编程吗
Rank: 1
等 级:新手上路
帖 子:31
专家分:0
注 册:2018-3-13
结帖率:33.33%
  问题点数:0  回复次数:4   
求时间复杂度
n++;

function( n );

int i, j;

for (i=0; i<n; i++){

    function(i);

}

for (i=0; i<n; i++){

    for(j=i; j<n; j++){

        cout<<"DS Cool!"<<endl;

    }

}
大佬们求这道题循环的次数以及时间复杂度
2018-09-09 16:16
请大师指点
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:3
帖 子:6
专家分:20
注 册:2018-9-13
  得分:0 
不好意思!你这代码,感觉有问题
2018-09-21 09:24
编程吗
Rank: 1
等 级:新手上路
帖 子:31
专家分:0
注 册:2018-3-13
  得分:0 
回复 2楼 请大师指点
这个是大话数据结构书上的
2019-01-21 23:08
firstbobo
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:54
专家分:101
注 册:2010-1-21
  得分:0 
这个了解吗;

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,
若有某个辅助函数f(n),使得T(n)/f(n)的极限值(当n趋近于无穷大时)为不等于零的常数,则称f(n)是T(n)的同数量级函数。
记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

随着模块n的增大,算法执行的时间的增长率和 f(n) 的增长率成正比,所以 f(n) 越小,算法的时间复杂度越低,算法的效率越高。
在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,

例:算法:

for(i=1; i<=n; ++i)
{
    for(j=1; j<=n; ++j)
    {
        c[i][j] = 0;//该步骤属于基本操作执行次数:n的平方次
        for(k=1; k<=n; ++k)
            c[i][j] += a[i][k] * b[k][j];//该步骤属于基本操作执行次数:n的三次方次
    }
}
则有   ,根据上面括号里的同数量级,我们可以确定 n的三次方 为T(n)的同数量级
则有  ,然后根据 T(n)/f(n) 求极限可得到常数c
则该算法的时间复杂度:T(n) = O(n^3) ;n^3即是n的3次方。

给的题有2个循环;要求哪个,还是总的;




2019-03-02 17:14
俺是你大爷
Rank: 2
等 级:论坛游民
帖 子:57
专家分:35
注 册:2019-3-12
  得分:0 
for循环有个结论,就是复杂度和循环嵌套的层数呈相应的倍数增加
2019-03-12 13:22







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

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