Redian新闻
>
一个貌似指数级的算法问题求更简单的算法
avatar
一个貌似指数级的算法问题求更简单的算法# JobHunting - 待字闺中
i*y
1
任意给定一个二进制数,比如10111,现在要打印出所有的非零位1的个数和等于k的二
进制数。
说得比较饶……
就比如给你10111,给定K=2,也就是说1的个数和只能等于2
那么就要输出:
10100, 10010, 10001, 00110, 00101, 00011,大概就是C(4,2)= 6这么多种组
合。
再比如给定10111,K=3
就要输出:
10110, 10101, 10011, 00111,一共C(4,3)= 4种.
我怎么想都觉得这个方法搞下去是指数级的(或者阶乘级的)复杂度,求简单的办法?
avatar
b*n
2
其实就是 a 个 0, b 个 1 有多少种排列,a b 已知
最小的排列是 0....0 (a 个) + 1...1 (b 个)
然后不断把最低位的 0 和他右侧最近的 1 互换,
最地低的 0 到 最右侧之后,倒数第二个 0 进行替换,
替换后把其右侧数字从新从 0 到 1 排列,然后重复上述过程,
直到最大的可能 b 个 1 + a 个 0,用递归好写一点

【在 i******y 的大作中提到】
: 任意给定一个二进制数,比如10111,现在要打印出所有的非零位1的个数和等于k的二
: 进制数。
: 说得比较饶……
: 就比如给你10111,给定K=2,也就是说1的个数和只能等于2
: 那么就要输出:
: 10100, 10010, 10001, 00110, 00101, 00011,大概就是C(4,2)= 6这么多种组
: 合。
: 再比如给定10111,K=3
: 就要输出:
: 10110, 10101, 10011, 00111,一共C(4,3)= 4种.

avatar
i*y
3
大概懂你意思了,这样用递归的话,时间复杂度是不是指数级的呢?
跪谢!~~~

【在 b******n 的大作中提到】
: 其实就是 a 个 0, b 个 1 有多少种排列,a b 已知
: 最小的排列是 0....0 (a 个) + 1...1 (b 个)
: 然后不断把最低位的 0 和他右侧最近的 1 互换,
: 最地低的 0 到 最右侧之后,倒数第二个 0 进行替换,
: 替换后把其右侧数字从新从 0 到 1 排列,然后重复上述过程,
: 直到最大的可能 b 个 1 + a 个 0,用递归好写一点

avatar
b*e
4
这个不是等价于m个index(index对应1的位置)中取k个怎么取。c(m,k)指数级别的结果
书目。
怎么样都是指数级别的运算吧?因为至少有个path是print ith number.大牛指正。
avatar
i*y
5
我也这么觉得的,等待大牛指正,看有没有什么牛逼算法。

【在 b*******e 的大作中提到】
: 这个不是等价于m个index(index对应1的位置)中取k个怎么取。c(m,k)指数级别的结果
: 书目。
: 怎么样都是指数级别的运算吧?因为至少有个path是print ith number.大牛指正。

avatar
b*n
6
最多 O(n^2)

【在 i******y 的大作中提到】
: 大概懂你意思了,这样用递归的话,时间复杂度是不是指数级的呢?
: 跪谢!~~~

avatar
b*n
7
当然不是,你并没有遍历所有可能

【在 b*******e 的大作中提到】
: 这个不是等价于m个index(index对应1的位置)中取k个怎么取。c(m,k)指数级别的结果
: 书目。
: 怎么样都是指数级别的运算吧?因为至少有个path是print ith number.大牛指正。

avatar
b*n
8

这里要有个排序的步骤,0 右侧的序列排序,变成
1 0 0 1 1 然后继续,这个排序因为只有两个数,所以复杂度是 O(n)

【在 i******y 的大作中提到】
: 我也这么觉得的,等待大牛指正,看有没有什么牛逼算法。
avatar
n*e
9
b 个 1只能在原来的数中 1出现的位置排,不是随便排的。

【在 b******n 的大作中提到】
: 其实就是 a 个 0, b 个 1 有多少种排列,a b 已知
: 最小的排列是 0....0 (a 个) + 1...1 (b 个)
: 然后不断把最低位的 0 和他右侧最近的 1 互换,
: 最地低的 0 到 最右侧之后,倒数第二个 0 进行替换,
: 替换后把其右侧数字从新从 0 到 1 排列,然后重复上述过程,
: 直到最大的可能 b 个 1 + a 个 0,用递归好写一点

avatar
i*y
10
这个用排列应该没错。
就是忽略掉原来数里面的0,只考虑里面的1
比如10111,里面一共有4个1,当k=2就是在这4个1里面选2个1出来

【在 n****e 的大作中提到】
: b 个 1只能在原来的数中 1出现的位置排,不是随便排的。
avatar
n*e
11
为啥最多是O(n^2)?
我觉得这个题怎么做都是指数级的,顶多算是pseudo polynomial.

【在 b******n 的大作中提到】
: 最多 O(n^2)
avatar
i*y
12
发现问题所在了,中间我miss掉了一步判断,不过这样一来我就不会分析时间复杂度了
,感觉不知道还是不是n^2
还是用上面的列子初始化:
0 01 1 1 // 3,4,5
首先从右向左遇到第一个01就把他替换成10:
0 10 1 1 // 2,4,5
同时要保证这个10右边的所有的临近的1都是在最右边的,这一步10后面两个1都在最右
,所以不用动。
算法继续,找到在 0 1 01 1 //2,4,5中的第一个01换成10,得到
0 1 10 1 // 2,3,5
这一步1在最右边,也不动,算法继续
0 1 1 10 // 2,3,4
这一步开始就需要移动位置了,原来是 01 1 1 0 //2,3,4,把01变成10后:
10 1 1 0,注意这个数的10后面有2个1,所以要把这两个1都放到最右边去,也就是说
把 10 1 1 0 => 10 0 1 1 // 1,4,5,这样得到的才是正确的中间步骤。
然后类似,算法继续:
1 0 1 0 1 // 1,3,5
1 0 1 1 0 // 1,3,4
1 10 1 0 => 1 10 0 1 // 1,2,5 (这一步也是要把10后面的1放到最右边去)
1 1 0 1 0 // 1,2,4
1 1 1 0 0 // 1,2,3
这个算法的确把10种可能C(5,3)=C (5,2) = 10全部找到了,但是因为中间多了一项
移位的运算,我就不是很看得懂时间复杂度是多少了(如果不移动的话,感觉应该还是
n^2的),大牛们指教下??
avatar
d*x
13
output is O(n chooses k), which is O(n^k).
So the algorithm should at least take O(n^k) time, for k == 2, you do not
need complex algorithm. just a double loop will give you all the answers.
for k > 2, you do not need to optimize -- anyway it is exp complexity.

【在 i******y 的大作中提到】
: 发现问题所在了,中间我miss掉了一步判断,不过这样一来我就不会分析时间复杂度了
: ,感觉不知道还是不是n^2
: 还是用上面的列子初始化:
: 0 01 1 1 // 3,4,5
: 首先从右向左遇到第一个01就把他替换成10:
: 0 10 1 1 // 2,4,5
: 同时要保证这个10右边的所有的临近的1都是在最右边的,这一步10后面两个1都在最右
: ,所以不用动。
: 算法继续,找到在 0 1 01 1 //2,4,5中的第一个01换成10,得到
: 0 1 10 1 // 2,3,5

avatar
b*n
14
上面说过了,这个移位是线性复杂度
所以整个还是 O(n^2)

【在 i******y 的大作中提到】
: 发现问题所在了,中间我miss掉了一步判断,不过这样一来我就不会分析时间复杂度了
: ,感觉不知道还是不是n^2
: 还是用上面的列子初始化:
: 0 01 1 1 // 3,4,5
: 首先从右向左遇到第一个01就把他替换成10:
: 0 10 1 1 // 2,4,5
: 同时要保证这个10右边的所有的临近的1都是在最右边的,这一步10后面两个1都在最右
: ,所以不用动。
: 算法继续,找到在 0 1 01 1 //2,4,5中的第一个01换成10,得到
: 0 1 10 1 // 2,3,5

avatar
i*y
15
受教了,看来不管怎么给不同的算法,exp是逃不掉的了

【在 d**********x 的大作中提到】
: output is O(n chooses k), which is O(n^k).
: So the algorithm should at least take O(n^k) time, for k == 2, you do not
: need complex algorithm. just a double loop will give you all the answers.
: for k > 2, you do not need to optimize -- anyway it is exp complexity.

avatar
d*x
16
errr so i have to fix my statement
it depends on how OP defines the problem -- whether k is fixed :D

【在 i******y 的大作中提到】
: 受教了,看来不管怎么给不同的算法,exp是逃不掉的了
avatar
i*y
17
好吧,你好像又说服我了,如果移位是线性的操作,那可能还是n^2.

【在 b******n 的大作中提到】
: 上面说过了,这个移位是线性复杂度
: 所以整个还是 O(n^2)

avatar
d*x
18
ok... n chooses 3 is n(n-1)(n-2)/6
how can you output n chooses 3 solutions in O(n^2) time?

【在 i******y 的大作中提到】
: 好吧,你好像又说服我了,如果移位是线性的操作,那可能还是n^2.
avatar
b*n
19
哈哈,算法是对的,不过复杂度还是要有点问题,
因为每次排序之后,从新开始,一个 0 可能多次经历替换过程,
所以循环的次数不一定为应该大于 n,所以应该高于 O(n^2)

【在 i******y 的大作中提到】
: 好吧,你好像又说服我了,如果移位是线性的操作,那可能还是n^2.
avatar
i*y
20
认真想了下,刚才那个算法,外层就相当于是一个冒泡算法,时间复杂度是n^2,稍微
和冒泡不同的是,他中间多了一个换位的步骤,虽然换位的步骤是线性变换,但估计变
完以后外层的loop也跟着变了,所以估计帅哥你是对的,还是exp级别。
另外我也考虑过组合公式问题,C(5,3)=C(5,2),所以如果按照exp来解释的话,那个
C(n,k)里面的k是不会超过n/2的,因为C(n,k)= C(n,n-k)。
好吧,我错了,不管C(n,k)还是 C(n,n-k),都是exp……
犯二了

【在 d**********x 的大作中提到】
: ok... n chooses 3 is n(n-1)(n-2)/6
: how can you output n chooses 3 solutions in O(n^2) time?

avatar
i*y
21
好吧,我错了,不管C(n,k)还是 C(n,n-k),都是exp……
犯二了
avatar
h*6
22
C(n,k)是下限,如果限定复杂度为C(n,k),还是很有难度的。
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。