algorithm - 如何确定此解决方案对重复排列的运行时间？

Question

我知道 n 个不同对象的排列数是 n!，所以最坏的情况，下面是 n!在运行时。但是平均情况呢？我有一个解决方案来处理具有重复项的数组的置换元素(例如 - [1, 2, 2, 3])，但我不确定如何确定平均情况下的运行时间。有人可以给我解释一下吗？

import collections
class Permutations(object):
    def permuteUnique(self, nums):
        ctr = collections.Counter(nums)
        res = []
        self.backtrack(res, [], nums, len(nums), ctr)
        return res

    def backtrack(self, res, temp, nums, check, ctr):
        if check == 0:
            res.append(temp)
        else:
            for key,v in ctr.items():
                if ctr[key] == 0:
                    continue
                ctr[key] -= 1
                self.backtrack(res, temp + [key], nums, check - 1, ctr)
                ctr[key] += 1

Answer 1

假设您有一个数组，其中 k 个不同的值出现在 m_1、m_2、...、m_k 次。让 n = m_1 + m_2 + ... + m_k。排列数是 n 不同事物的排列数除以给出相同排列的排列数。由于每个不同的值都可以以任何顺序出现并给出相同的排列，所以结果是 n!/(m_1!* m_2!* ... * m_k!)

如果您想从这个精确的公式得出某种有用的近似值，我建议您使用 Stirling's Approximation ，坚持你想要的假设，然后从那里开始。