应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台» 网络生活区» 有奖问答 » 有奖问答完结子版 » 数据结构中复杂度的计算
71/1返回列表
查看: 1637  |  回复: 6
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 1 个 博学EPI ，点击这里进行查看

简单疯狂

金虫 (小有名气)

[求助] 数据结构中复杂度的计算

1.Assume array A contains n values,that Random takes constant time,and that sort takes nlogn steps.
for (i=0;i<n;i++){
     for(j=0;j<n;j++)
         A=Random(n);
             sort(A,n);
}
2.sum=0;
if(EVEN(n))
   for(i=0;i<n;i++)
      sum++;
else
    sum=sum+n;
麻烦各位大神帮忙解答这两题的复杂度分别是多少，谢谢！
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
经验告诉我，求人不如求己
1楼 2013-12-30 00:24:32
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

laohuajiang

至尊木虫 (职业作家)

老花匠

【答案】应助回帖

★ ★ ★ ★ ★ ★
简单疯狂: 金币+6, 博学EPI+1 2013-12-31 21:32:36
1。 n*(n*constant+n*log(n))
赞一下 回复此楼
静坐常思自己过,闲谈莫论他人非!---老花匠(老非老-春残意彷徨;花非花-芳踪觅繁华,匠非匠-最美难得糊涂!)
2楼2013-12-30 08:43:23
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

neuer

金虫 (小有名气)

【答案】应助回帖

★ ★ ★ ★
简单疯狂: 金币+4 2013-12-31 21:32:43
2. worst-case time complexity O(n)
赞一下 回复此楼
3楼2013-12-30 10:11:55
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

简单疯狂

金虫 (小有名气)
引用回帖:
2楼: Originally posted by laohuajiang at 2013-12-30 08:43:23
1。 n*(n*constant+n*log(n))

能否给出具体求解？
赞一下 回复此楼
经验告诉我，求人不如求己
4楼2013-12-30 18:44:42
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

简单疯狂

金虫 (小有名气)
引用回帖:
3楼: Originally posted by neuer at 2013-12-30 10:11:55
2. worst-case time complexity O(n)

题目中没说明最好还是最差的情况，那怎么办？
赞一下 回复此楼
经验告诉我，求人不如求己
5楼2013-12-30 18:45:42
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

laohuajiang

至尊木虫 (职业作家)

老花匠
引用回帖:
4楼: Originally posted by 简单疯狂 at 2013-12-30 18:44:42
能否给出具体求解？...

for (i=0;i<n;i++)                         n
{
     for(j=0;j<n;j++)                    n
         A=Random(n);                   const
      ort(A,n);                              n*log(n)
}

n^2*log(n)
赞一下(1人) 回复此楼
静坐常思自己过,闲谈莫论他人非!---老花匠(老非老-春残意彷徨;花非花-芳踪觅繁华,匠非匠-最美难得糊涂!)
6楼2013-12-30 18:50:18
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

简单疯狂

金虫 (小有名气)
引用回帖:
6楼: Originally posted by laohuajiang at 2013-12-30 18:50:18
for (i=0;i<n;i++)                         n
{
     for(j=0;j<n;j++)                    n
         A=Random(n);                   const
      ort(A,n);                              n*log(n) ...

谢谢！
回复此楼
经验告诉我，求人不如求己
7楼2013-12-31 21:32:18
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 简单疯狂 的主题更新
71/1返回列表
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[基金申请] 小木虫上这么多卖论文的，真有人买论文么？感觉没必要啊 +4 Tide man 2026-08-10 4/200 2026-08-11 07:45 by emeraldine
[基金申请] 为什么网上很多人说本周 12号出结果 +4 瞬息宇宙 2026-08-10 4/200 2026-08-11 02:02 by 旁观2020
[基金申请] 帮忙看看fileCode +4 wwncly 2026-08-10 8/400 2026-08-10 22:07 by demonstreets
[基金申请] FileCode能看出啥？ +7 要乐观耀哥 2026-08-10 15/750 2026-08-10 19:29 by 要乐观耀哥
[基金申请] 确定了，国自然21号放榜 +6 布布和一二 2026-08-10 7/350 2026-08-10 19:15 by 2000zf36392
[基金申请] 静等基金结果 +5 gjjjzhong 2026-08-10 16/800 2026-08-10 17:19 by Tide man
[基金申请] 应该是93bebmhtak前后十一个字符比较关键 +14 Lanmanbaby 2026-08-09 22/1100 2026-08-10 14:57 by wwncly
[基金申请] 奇怪，两个人的filecode固定段从头到尾一模一样 +4 布布和一二 2026-08-10 4/200 2026-08-10 14:50 by 医学老男孩
[基金申请] 好奇怪的filecode +4 布布和一二 2026-08-08 5/250 2026-08-10 14:20 by 冰心玉壶晴
[基金申请] 这样的filecode谁见过 +11 布布和一二 2026-08-08 22/1100 2026-08-10 11:10 by wmfsnow
[基金申请] fileCode有新解读？ +10 Tide man 2026-08-08 18/900 2026-08-09 12:55 by 仁砚薪传
[基金申请] 关于filecode，很负责任的告诉大家 +6 爱看书的可乐 2026-08-08 7/350 2026-08-08 22:13 by a_niu
[基金申请] 关于豆爷回答的JTJC与%2F数量 +5 yang182083 2026-08-06 7/350 2026-08-08 18:29 by zhanghaozhu
[基金申请] 国基金的申报应该改成非等额制，评价高的钱多评价低的钱少，但是增加资助率 +7 a089 2026-08-07 7/350 2026-08-08 18:05 by gltch
[基金申请] 关于filecode +4 布布和一二 2026-08-07 7/350 2026-08-07 22:55 by zhanghaozhu
[基金申请] 化学口download_prp&amp;fileCode的固定段好像这几天一直没变，有变的大神么？ +3 Tide man 2026-08-07 4/200 2026-08-07 22:39 by Tide man
[基金申请] 大家散了吧，后缀研究没有意义，别浪费时间了，过好目前的每一天，不要焦虑 +5 Tide man 2026-08-06 7/350 2026-08-07 13:11 by 医学老男孩
[基金申请] filecode +14 等待解的谜 2026-08-06 19/950 2026-08-07 12:20 by wlwhappy
[基金申请] filecode +8 布布和一二 2026-08-06 11/550 2026-08-06 20:41 by tangpu318
[基金申请] 好消息？这个有何含义？？？ +8 Tide man 2026-08-05 10/500 2026-08-05 16:14 by xmuxiaoyu
信息提示
关闭
请填处理意见
关闭