子集 - 时间/空间分析
问题是为给定的整数阵列生成子集。
例如，
输入： [0，1，2]
输出： [[]，[0]，[1]，[ 2]，[0,1]，[0,2]，[1，2]，[0，1，2]]
我想帮助分析解决方案的时间和空间复杂性解决此问题。
时间复杂性
就像我知道子集的总数为2^n，因此时间复杂性至少为2^n，然后是我的树高度就像在n处一样最糟糕的案例，但是后来我正在执行2个嵌套环内的递归依赖于n ...所以我想知道我的时间复杂性是否像O（2^n * n^3）？好吧，如果是这样...我的代码非常糟糕。
空间复杂性
该空间将消耗2^n行和最多元素，因此我知道空间复杂性将为O（2^n * n）。
请让我知道II是否误解了任何东西！谢谢。
def powerset(array):
# Write your code here.
start_len = 0
answer = [[]]
while(start_len <= len(array)):
i = 0
while(i < len(array)):
print(array[i:])
powersetHelper([], array[i:], start_len, answer)
i += 1
start_len += 1
print(answer)
return answer
def powersetHelper(chosen, choices, target_len, answer):
# Write your code here.
chosen.append(choices[0])
if(len(chosen) == target_len):
if(chosen not in answer):
answer.append(chosen)
else:
i = 1
while(i < len(choices)):
chosen_copy = chosen.copy()
powersetHelper(chosen_copy, choices[i:], target_len, answer)
i += 1
The problem was to generate the subsets for a given array of integers.
For example,
input: [0, 1, 2]
output: [[], [0], [1], [2], [0,1], [0,2], [1, 2], [0, 1, 2]]
I wanted help on analyzing the time and space complexity of my solution for this problem.
Time Complexity
Like I know that the total number of subsets would be 2^N so the time complexity would be at least 2^N and then the height of my tree would be like worst-case at N, but then I am executing the recursion inside 2 nested loop dependent on N...So I was wondering if my time complexity would be like O(2^N * N^3)? Well, if that was the case ... my code is pretty bad.
Space Complexity
The space would consume 2^N rows and at most N elements, so I understand that the space complexity would be O(2^N * N).
Please let me know if iI misunderstood anything! Thank you.
def powerset(array):
# Write your code here.
start_len = 0
answer = [[]]
while(start_len <= len(array)):
i = 0
while(i < len(array)):
print(array[i:])
powersetHelper([], array[i:], start_len, answer)
i += 1
start_len += 1
print(answer)
return answer
def powersetHelper(chosen, choices, target_len, answer):
# Write your code here.
chosen.append(choices[0])
if(len(chosen) == target_len):
if(chosen not in answer):
answer.append(chosen)
else:
i = 1
while(i < len(choices)):
chosen_copy = chosen.copy()
powersetHelper(chosen_copy, choices[i:], target_len, answer)
i += 1
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
该代码实际上是
ω（n * 4^n）（即至少在此运行时），仅仅是因为每次添加新子集时都会在所有子集上执行线性搜索的两行。如果您的输入列表没有重复项，并且您已经编写了PowerSet算法以避免重复，那么这些行是不必要的。无论哪种方式，请使用
set（）而不是用于遏制检查的列表，因为这是迄今为止的运行时。theta（n * 2^n）的空间复杂性是正确的；如果您存储所有子集，这将是最佳的。不幸的是，我不知道该围护检查问题是否解决了代码的时间复杂性。看来，在PowerSet和PowerSethper中执行了大量不必要的工作和递归调用，并且遵循算法的逻辑很难。从经验测试（将全局计数器放在功能中）中，固定控制检查后的操作数量非常非常接近于n^2 * 2^n的常数倍数。This code is actually
Ω(N * 4^N)(i.e. at least this runtime), only because of the two lineswhich perform a linear search over all subsets every time a new subset is added. If your input list has no duplicates and you've written the powerset algorithm to avoid repeats, these lines are unnecessary. Either way, use a
set()instead of a list for containment checks, as this by far dominates the runtime.The space complexity of
Theta(N * 2^N)is correct; this is optimal if you're storing all subsets. Unfortunately I don't know the time complexity of the code if that containment check problem is fixed. It looks like a large amount of unnecessary work and recursive calling is performed in powerset and powersetHelper, and I'm having a hard time following the logic of the algorithm. From empirical testing (putting global counters in the function), the number of operations after fixing the containment check grows very very closely to a constant multiple of n^2 * 2^n.