Какова временная сложность этой функции, которая генерирует все уникальные комбинации факторов числа?

Question

Здравствуйте, я только что решил leetcode 254 [https://leetcode.com/problems/factor-combinations/], цель этого алгоритма - найти все уникальные комбинации факторов для данного числа n (пример: для n = 8 мы возвращаем [[2 x 2 x 2], [2 x 4]])и написал следующий код:

def getFactors(self, n: int) -> List[List[int]]:
    def helper(n, cur, path, ind, factors):
        if cur == n:
            res.append(path[:])
            return

        for i in range(ind, len(factors)):
            if cur * factors[i] <= n:
                path.append(factors[i])
                helper(n, cur * factors[i], path, i, factors)
                path.pop()

    res = []
    helper(n, 1, [], 0, [num for num in range(2, n) if n % num == 0])
    return res if res != [[]] else []

Способ работы этого алгоритма заключается в том, что я перебираю все факторы и умножаю cur на коэффициент, над которым я перебираю, и до тех пор, пока cur * factors[i] <= n я могу добавить, чтос учетом моего path и продолжаю повторяться.

Хотя я не могу понять сложность времени в терминах n. Я могу сказать, что в худшем случае дерево рекурсии будет иметь глубину log n (это было бы 2 x 2 x 2 ... x 2, если n - степень 2), но я застрял в понимании фактора ветвления для этого дерева.

Любая помощь в расчете временной сложности этого алгоритма приветствуется, но я был бы очень признателен за интуитивный способ взглянуть на него (то, что я могу воспроизвести в интервью) ... более формальные методы такжедобро пожаловать.

РЕДАКТИРОВАТЬ 1:

Таким образом, я могу сказать, что это повторение имеет log(n) ответвлений (количество факторов) и log(n) глубину в худшем случае, что приводит к времени выполнения O(log(n)^log(n))это рассуждение хорошо?

РЕДАКТИРОВАТЬ 2:

Однако другой способ взглянуть на это, у нас есть O(log(n)) факторов, и мы просто делаем подмножество всех возможных комбинаций, что является2^n упражнение, в результате чего 2^log(n) = n различных решений. И для каждого из n решений у нас есть log(n) (глубина дерева) умножения, приводящие к O(nlog(n)) времени выполнения ... поэтому мой вопрос -> Какой анализ является правильным?

Answer 1

Одно наблюдение:

Число факторов n в худшем случае происходит, когда n является произведением последовательного числа наименьших простых чисел. Т.е. 2 * 3 * 5 * 7 * 11 и т. Д.

Мне было любопытно, насколько быстро растет это число в зависимости от n (опять же, в худшем случае). Используя Python и глядя на первые 100 или около того простых чисел, кажется, что основанный на 10 логарифм n растет немного быстрее, чем число факторов в n. Для малых значений числа почти одинаковы, но разница продолжает увеличиваться, и после 70 или около того факторов (то есть - произведение 70 первых простых чисел) логарифм более чем вдвое превышает число факторов.

Другой способ выразиться в том, что [number of factors of n] растет медленнее, чем log n.

Answer 2

Общий случай сложности времени равен T(n) = sum_{i=1}{number of factors of n}(T(n/f_i)) + c (f_i s - это факторы n). Если n = 2^k, сложность времени равна T(n) = log(n) T(n/2) + c. Следовательно:

T(n) = log(n) T(n/2) + c = 
       log(n) (log(n/2) T(n/2^2) + c) + c = 
       log(n) log(n/2) T(n/2^2) + c (1 + log(n)) = 
       k * (k-1) * T(n/2^2) +‌c (1 + k) = 
       k * (k-1) * (log(n/2^2) T(n/2^3) + c) + c (1 + k) = 
       k * (k-1) * (k-2) T(n/2^3) +‌c (1 + k + k * (k-1)) = Omega(log(n)!)

Мы использовали Omega, потому что это только для случая 2^k. Чтобы узнать больше о сложности, вам нужно больше изучить общий термин.