数组幂集的时间复杂度分析：含for循环的递归方法探究

幂集是指数组所有子集构成的集合，比如数组[1,2]的幂集为[[],[1],[2],[1,2]]，其大小为2^n（n为数组长度）。已知第一种递归实现通过对每个元素做“选或不选”的两次递归调用，递推关系为T(n) = 2T(n-1) + O(1)，时间复杂度为O(2^n)。现在针对以下含for循环的递归实现，推导其时间复杂度及对应的递推关系：

class Solution:
    
    def helperSubsets(self,output_li, nums, klist):
        output_li.append(klist)
        for i in range(len(nums)):
            self.helperSubsets(output_li,nums[i+1:],klist+[nums[i]])
    
    def subsets(self, nums: List[int]) -> List[List[int]]:
        output_li = []
        self.helperSubsets(output_li,nums,[])
        return output_li

递推关系推导 #

定义T(n)为处理长度为n的数组时，helperSubsets方法的总时间开销（包含所有递归调用）：

1. 基准情况：当n=0（空数组）时，方法仅执行output_li.append(klist)，时间开销为O(1)，即T(0)=O(1)。
2. 递归情况：
   • 首先执行一次append操作，开销为O(1)。
   • 接着进入循环，循环次数为n次。第i次循环时，传入的子数组长度为n-i-1，对应的递归调用开销为T(n-i-1)。
   • 因此总开销的递推式为：

     T(n) = 1 + T(n-1) + T(n-2) + ... + T(0)
     

   式中的1对应append操作的O(1)开销，求和项是循环内所有递归调用的总开销。

时间复杂度推导 #

通过递推式展开找规律：

• T(n) = 1 + T(n-1) + T(n-2) + ... + T(0)
• T(n-1) = 1 + T(n-2) + ... + T(0)

将两式相减可得：
T(n) - T(n-1) = T(n-1) → T(n) = 2*T(n-1)

结合基准情况T(0)=1，可解得T(n)=2^n，因此该方法的时间复杂度为O(2^n)。

注：若计入klist+[nums[i]]创建新列表的开销，每个子集的平均长度为n/2，总开销会变为O(n*2^n)，但通常讨论幂集生成的时间复杂度时，默认以子集数量为基准，核心复杂度仍为O(2^n)。

内容的提问来源于stack exchange，提问作者Rishabh Sharma