时间戳

首页 > 解决方案 > Leetcode 78 - 生成幂集时间复杂度

python - Leetcode 78 - 生成幂集时间复杂度

问题描述

Leetcode 78题的潜在解法：

class Solution(object):
    def __init__(self):
        self.map = {}
    
    def helper(self, count, nums, vals, result):       
        
        if count == 0:
            result += [vals]        
            
        for i in range(len(nums)):
            self.helper(count - 1, nums[i+1:], vals + [nums[i]], result)
        
    
    def subsets(self, nums):
        result = []
        result.append([])
        
        for count in range(1,len(nums)+1):
            self.helper(count, nums, [], result)   
            
        return result

对于上述解决方案，时间复杂度是 O(2^n) 还是 O(n * 2^n) ？

标签： pythonalgorithmtime-complexitycode-complexity

解决方案

可以通过查找不同N的函数调用次数来找出复杂性helper，代码方面如下所示：

class Solution(object):

    def __init__(self):
        self.map = {}
        self.counter = 0

    def helper(self, count, nums, vals, result):
        self.counter += 1
        if count == 0:
            result += [vals]

        for i in range(len(nums)):
            self.helper(count - 1, nums[i + 1:], vals + [nums[i]], result)

    def subsets(self, nums):
        result = [[]]

        for count in range(1, len(nums) + 1):
            self.helper(count, nums, [], result)

        return self.counter

因此对于：

ñ 调用辅助函数的时间
1 2
2 8
3 24
4 64
5 160
6 384
7 896
8 2048
9 4608
10 10240
... ……
ñ O(n * 2^n)

该helper函数的复杂性为O(2^n)并且因为您调用了 list 的每个元素nums：

for count in range(1,len(nums)+1):
    self.helper(count, nums, [], result)

总时间复杂度为O(n * 2^n)

推荐阅读