Как определить время выполнения этого решения для дублирования перестановок? - PullRequest
Новая
       13

Как определить время выполнения этого решения для дублирования перестановок?

0 голосов
/ 09 ноября 2018

Я знаю, что число перестановок на 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

1 Ответ

0 голосов
/ 10 ноября 2018

Предположим, что у вас есть массив с k различными значениями, встречающимися m_1, m_2, ..., m_k раз. Пусть n = m_1 + m_2 + ... + m_k. Количество расположений - это число перестановок n различных вещей, деленное на количество перестановок, которые дают одинаковое расположение. Поскольку каждое из отдельных значений может появляться в любом порядке и иметь одинаковое расположение, получается n! / (m_1! * m_2! * ... * m_k!)

Если вы хотите перейти от этой точной формулы к какой-то полезной аппроксимации, я бы предложил использовать Аппроксимация Стирлинга , придерживаясь желаемых допущений и переходя оттуда.

...