Блог

Вопрос 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)?

Можно узнать сложность, посмотрев 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
 

Итак, для:

helper Функция имеет сложность O(2^n) и поскольку вы вызывали для каждого элемента списка nums :

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

общая временная сложность O(n * 2^n)