该算法（解决 leetcode 问题 650）的时间复杂度是多少？

Question

您好，我一直在研究 https://leetcode.com/problems/2-keys-keyboard/submissions/ 并遇到了这个动态规划问题。

您从空白页上的 'A' 开始，完成后您会得到一个数字 n，页面上应该有 n 次 'A'。问题是你只允许 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) 之间，因为在第二个循环中我们要 "faster" 而不是 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的最大质因数。

该算法（解决 leetcode 问题 650）的时间复杂度是多少？

What is the time complexity of this agorithm (that solves leetcode question 650)?

algorithm

dynamic-programming

data-structures

python-3.x

bottom-up