Какова временная сложность этого агорифма (который решает вопрос кода leetcode 650)?

Question

Здравствуйте, я работал над https://leetcode.com/problems/2-keys-keyboard/submissions/ и натолкнулся на этот вопрос о динамическом программировании.

Вы начинаете с 'A' на пустой странице, и вы получаете число n, когда выГотово, вы должны иметь n раз «А» на странице.Подвох в том, что вам разрешено копировать только 2 операции (и вы можете копировать только общее количество A, находящихся в данный момент на странице) и вставлять -> найти минимальное количество операций, чтобы получить n 'A' на странице.

Я написал следующий алгоритм, который решает проблему, но мне сложно анализировать его временную сложность.

Вот код:

    def minSteps(self, n: int) -> int:
        DP = [0] + [0] + [i for i in range(2, n+1)]

        for d in range(2, n+1):
            for i in range(d*2, n+1, d):
                DP[i] = min(DP[i], DP[d] + i//d )
        return DP[n]

Итак, моя интуиция говоритэтот алгоритм находится между O(n^2) и O(nlogn), так как во втором цикле мы идем "быстрее", чем O(n), однако, поскольку размер шага d не удваивается между каждой итерацией, он все равно O(n) в некоторой степени длявторой цикл ...

Я не уверен, как его проанализировать, любая помощь приветствуется.

Answer 1

Давайте посмотрим на внешний цикл - он выполняется O(N) раз.
Каждый внутренний цикл выполняет O(N / d) операций, поскольку скачки индекса находятся в d.
Таким образом, вычисление:

N / 1 + N / 2 + N / 3 + ... + 1

Обратите внимание, что в этой сумме N предметов.

Мы можем вывести N из:

N * (1 / 1 + 1 / 2 + 1 / 3 + ... + 1 / N)

, что примерно равно:

N * ln N

(Интуиция заключается в том, что, интегрируя функцию 1 / N, вы получите ln)

Таким образом, сложность во всем составляет O(N log N)

Answer 2

Ваше решение O(nlogn). Вот более эффективное решение:

 def minSteps(self, n: int) -> int:
        ans = 0
        d = 2
        while n >= d * d:
            while n % d == 0:
                ans += d
                n //= d
            d += 1
        if n != 1:
            ans += n
        return ans 

Это решение основано на решении, размещенном на LeetCode, но гораздо быстрее. Сложность времени равна O(sqrt(p)), где p - это наибольший простой коэффициент n.