python-3.x - 该算法(解决 leetcode 问题 650)(问题 2)的时间复杂度是多少？

Question

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

您从空白页上的“A”开始，完成后得到一个数字 n，页面上应该有 n 次“A”。要注意的是，您只能进行 2 次复制操作(并且您只能复制当前页面上 A 的总数)和粘贴 --> 找到在页面上获得 n 个“A”的最少操作数。

我解决了这个问题，但后来在 leetcode 的讨论部分找到了更好的解决方案 --> 我无法弄清楚它的时间复杂度。

    def minSteps(self, n):
        factors = 0
        i=2
        while i <= n:
            while n % i == 0:
                factors += i
                n /= i
            i+=1
        return factors

它的工作方式是 i 永远不会大于 n 的最大质因数 p 所以外层循环是 O(p) 并且内部 while 循环基本上是 O(logn)，因为我们在每次迭代时划分 n/= i。

但是在我看来，我们在内循环中总共进行了 O(logn) 的划分，而外循环是 O(p)，所以使用聚合分析这个函数基本上是 O(max(p, logn)) 这是正确的吗？

欢迎任何帮助。

Answer 1

你的推理是正确的:O(max(p, logn)) 给出了时间复杂度，假设算术运算需要常数时间。这个假设对于任意大的 n 是不正确的，它不适合机器的固定大小的数字存储，并且你需要具有 non-constant 的大整数操作。时间复杂度。但我会忽略这一点。

用 p 表示复杂度仍然很奇怪，因为它不是输入(而是从中导出)。您的输入只有 n，因此单独用 n 来表达复杂性是有意义的。

最坏情况

显然，当 n 为质数时，算法为 O(n) -- 内部循环从不迭代。

对于素数 n，算法将比 n+1 花费更多的时间，因为即使是 n+1 的最小因数(即 2)，会将外循环的迭代次数减半，但在内循环中只添加 1 个常量工作 block 。

所以 O(n) 是最坏的情况。

平均情况

对于一般情况，我们注意到 n 的除法发生的次数与 n 具有质因数(计算重复项)的次数一样多。例如，对于 n = 12，我们有 3 个分区，如 n = 2·2·3

average number of prime factors对于 1 < n < x 接近 loglogn + B，其中 B 是某个常数。所以我们可以说内循环的总执行的平均时间复杂度是O(loglogn)。

我们需要添加外循环的执行。这对应于平均最大素数。对于 1 < n < x this average approaches C.n/logn ，所以我们有:

O(n/logn + loglogn)

现在 n/logn 是这里更重要的术语，所以这简化为:

O(n/logn)