请问这个算法时间复杂度是否为 O(n!)

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 3128 天前的主题，其中的信息可能已经有所发展或是发生改变。

对于字符串的所有字符组合，我设计了如下算法：
eg."abc"

abc
ab, ac, bc
a, b, c
可见下层是上层每个结果去除一个字符，经过去重得到的结果。

那么程序可以这样写

递归函数名（字符串）｛
__保存字符串；
__for 循环对字符串遍历｛
____函数：删除该字符串中的某位置字符，返回新字符串____//此处被运算总计 n!次
____if 判断新字符串长度>1 则，
______递归函数（新字符串）
____否则，保存新字符串
__｝
｝

如注释，该算法的渐近时间复杂度即为 O(n!)

函数

算法

abc

符

9 条回复 • 2015-10-12 09:02:26 +08:00

zzy8200

2015-10-11 17:20:27 +08:00 via iPhone

为什么不用 2^n 算法？

luoway

2015-10-11 17:24:58 +08:00

@zzy8200 不会……

zzy8200

2015-10-11 23:35:30 +08:00 via iPhone

@luoway
for i=1 to 2^n-1
k=二进制(i)
然后用 k 给字符串做 mask ，保留 1 的位
输出
done

例： abc
i=7 （ 111 ）

abc
111

->abc

i=6 (110)
abc
110

->ab

luoway

2015-10-11 23:40:51 +08:00

@zzy8200 这种情况下二进制确实好用！多谢指点！

edfward

2015-10-12 00:45:02 +08:00

题：[Subsets on LeetCode]( https://leetcode.com/problems/subsets/)
解法：[Power Set - GeeksforGeeks]( http://www.geeksforgeeks.org/power-set/)

luoway

2015-10-12 01:00:52 +08:00 via Android

@edfward 没刷过题-_-||

ryd994

2015-10-12 04:54:46 +08:00 via Android

其实不用二进制也行，还是递归
你的问题主要是有重复解
ab 去掉 b 和 ac 去掉 c 都是一样的
可以反过来，递加
a b c
ab ac bc
abc
当考虑两个字母的解的时候，只考虑当前字母往后的。比如考虑 b 开头的解，就不需要考虑 ba ，因为 ab 肯定包含

imcoddy

2015-10-12 07:46:14 +08:00

@edfward 赞。其实这题的 Discuss 里面也有人提出了这个做法的。虽然我刷这题的只是弱弱地用了 Backtracking

luoway

2015-10-12 09:02:26 +08:00 via Android

@ryd994 正序考虑过，想的是在长度 4 以上的时候先求出含 a 的所有情况(长度 1,2,3)，再求不含 a 的。比较复杂。于是倒序想到这个算法。
现在使用每层长度只变 1 ，发现正序递加也能算。
如 abcd
a b c d
ab ac ad bc bd cd
abc abd acd bcd
abcd
没有重复，比递减更好。
多谢指点！