1

您好，我一直在研究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)因为在第二个循环中我们比“更快”，O(n)但是由于每次迭代之间步长d不会加倍，所以O(n)对于第二个循环来说仍然有点......

我不确定如何分析那个，欢迎任何帮助。

4

2 回答 2

2

让我们看看外部循环——它被执行了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)

于 2019-06-26T22:11:51.720 回答
0

您的解决方案是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。

于 2019-06-27T01:20:15.677 回答