Какова временная сложность этой функции powerset?

Question

Я решил этот вопрос (функция powerset) из leetcode https://leetcode.com/problems/subsets/submissions/, и вот мое решение:

    def subsets(nums):
        res = []
        n = len(nums)
        for subset_id in range(2**n):
            tmp = []
            for index in range(n):
                if 1 << index > subset_id:
                    break
                if subset_id >> index & 1:
                    tmp.append(nums[index])
            res.append(tmp)
        return res

Мне трудно анализировать временную сложность этого кода, утверждениеif 1 << index > subset_id: break делает это в соответствии с O(n*2^n) Я думаю, но все ли сводится к O(2^n)?Я не знаю, сложно ли это сказать.

Answer 1

Если мы предположим, что внутренний цикл будет проходить примерно половину range(n), прежде чем каждый раз нажимать break, то это O(n/2*2^n), что на самом деле все еще O(n*2^n). Это работает для любой фиксированной доли цикла, поэтому, даже если она составляет в среднем одну десятую range(n) вместо половины, она все равно O(n*2^n)