首页 > 试题广场 >

一个优化的程序可以生成一n个元素集合的所有子集，那么该程序的

[单选题]
一个优化的程序可以生成一n个元素集合的所有子集，那么该程序的时间复杂度是 
  • O(n!)
  • O(2^n)
  • O(n^2）
  • O(n*log(n))
查看正确选项
添加回答
agjsytt头像 agjsytt
求程序的时间复杂度，等价于寻找程序的语句执行次数随输入规模n的变化规律
我这么理解本题:假设该优化程序的生成一子集的流程如下:
Step1. 生成n个元素的所有子集. 这一步要生成2^n个子集.
Step2. 选择一个子集.这一步由于耗时很少，运行时间忽略.
那么现在只需关注Step1了. 
输入规模n 语句执行次数T(n)
1 2
2 2*2
n 2*2*2...*2. (n个2)
所以T(n)=O(2^n).

发表于 2017-02-19 22:33:30 回复(0)
更多回答
安于乔头像 安于乔
选B，每个元素分出现和不出现的两种情况，就是2的n次方
发表于 2015-08-09 18:12:46 回复(0)
木东2015头像 木东2015
选B
集合有{a，b，c，d}4个元素。它生成的子集有：空集，{a}，{b}，{c}，{d}，{a,b}，{a,c}，{a,d}，{b,c}，{b,d}，{c,d}，{a,b,c}，{a,b,d}，{a,c,d}，{b,c,d}，{a,b,c,d}16个
即2^4个。
发表于 2015-07-30 10:39:11 回复(3)
我不是匠人头像 我不是匠人
求一个集合的子集，有确定公式2^n个，所以复杂度为O（2^n）
发表于 2016-01-17 08:36:06 回复(0)
小狼狗刷刷题头像 小狼狗刷刷题
Cn,0+Cn,1+Cn,2+...+Cn,n = 2^n
发表于 2019-08-16 15:09:43 回复(0)
黏黏糖头像 黏黏糖
每个元素分为出现和不出现两种情况，时间复杂度为O(2^n)
发表于 2017-06-19 19:28:57 回复(0)
长寿村村民头像 长寿村村民
大意了，注意是 所有 子集… A是生成所有排列的时间复杂度。
发表于 2021-03-29 13:19:19 回复(0)
李维康头像 李维康
想错了。。。
编辑于 2016-09-12 11:24:33 回复(1)
huixieqingchun头像 huixieqingchun
每个元素分为出现和不出现两种情况
发表于 2016-05-13 12:45:10 回复(0)
最美头像 最美
可以借鉴这个算法http://blog.csdn.net/naturebe/article/details/7487394
发表于 2015-10-28 16:53:24 回复(0)
eagle头像 eagle
C

子集个数是n2量级的
发表于 2015-01-09 21:07:54 回复(1)
提交观点

问题信息

复杂度 阿里巴巴
上传者：稀里哗啦
难度：
11条回答 9512浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号