迭代算法的时间复杂度

Question

我有一个迭代算法，在每次迭代中计算量逐渐减少。以下是我的算法示意图：

输入大小：n 和 总迭代次数：k

iter 1: time taken -> f1 * n
iter 2: time taken -> f2 * n
iter 3: time taken -> f3 * n
...
iter k: time taken -> fk * n

其中f1 > f2 > f3 >...> fk且0 <= f1, f2,...,fk <= 1

问题：该算法的时间复杂度是什么？是否为Big-O(klog n)？

更新：

我认为问题似乎很模糊。我将用文字解释：

我的算法输入为n，我将在k次迭代中运行它。但每次迭代中，输入大小都会减少一个未知的因素。没有减小的模式。

例如：

iter 1: input size = n (always n)
iter 2: input size = n/2 (can change)
iter 3: input size = n/5 (can change)
iter 4: input size = n/8 (can change)
...
iter k: input size = n/10 (can change)

- Maggie

---

不，我正在尝试改进 Teofilo F. GONZALEZ（1985）的“最远点选择”算法，其时间复杂度为 Big-O(kn)。 - Maggie

问题：fi是依赖于n还是k的？ - Michael Graczyk

fi取决于n。我已经在问题中添加了更多信息。谢谢。 - Maggie

分母总是整数还是可以是实数？ - Michael Graczyk

让我们在聊天室里继续这个讨论。 - Michael Graczyk

Answer 1

给出的信息不足，我们只能确定复杂度为O((f1+ ... + fk)*n)¹。

为什么呢？我将通过两个fi的例子来说明，每个例子都会给出不同的复杂度：

案例1： fi = 1/2^i 在这种情况下，我们得到 n * 1/2 + n* 1/4 + ... + n*1/2^k < n，算法是 O(n) 案例2： fi = 1/i 在这种情况下，我们得到一个调和级数：n * 1/2 + n*1/3 + ... + n*1/k = n(1/2+1/3+...+1/k) = O(nlogk)。

编辑: 根据你的评论和编辑，如果我理解正确，算法运行的最坏情况是：

iter1 -> n ops
iter2 -> n/2 ops
iter3 -> n/3 ops
...
iterk -> n/k ops

如果这确实是情况，那么它与描述的case2相符，总运行时间是一个调和级数：n + n/2 + n/3 + .. + n/k = n(1 + 1/2 + 1/3 + ... + 1/k)，这是O(nlogk)。

---

(1) 严格数学意义上来说，大O表示一个上渐近界限，因为fi <= 1，我们可以推断算法是O(nk)，但它不是一个严格的界限，因为示例表明，不同的fi值可以给出不同的严格界限。

- amit

Answer 2

编辑

更具体地说：

如果您的示例中有分母：

iter 1: input size = n (always n)
iter 2: input size = n/2 (can change)
iter 3: input size = n/5 (can change)
iter 4: input size = n/8 (can change)
...
iter k: input size = n/10 (can change)

如果序列Xn是严格整数，那么它的时间复杂度是O(n*log k)。这是为什么呢？对于一个序列Xn要是O(Yn)，必须存在一些实数M和整数m，使得对于所有n > m，都有Xn < M*|Yn|。

现在考虑序列K = {1, 1/2, 1/3, ... 1/k} 和序列N = {1, 2, 3, 4...}。让Yn = N^t * K（这是N和K的外积），不论fi值如何，这个序列Yn始终大于你的序列。

因此，Xn < 1 * |Yn|，其中Yn是调和级数乘以n。正如阿米特所指出的，Yn落在O(n*log k)中，因此Xn也是如此。由于我们无法更紧密地限制Xn的上限，因此Xn的最佳极限近似也是O(n*log k)。

- Michael Graczyk

---

fk 不是常数，如果 f1,..., fk 具有 Zeno 特性，则它非常重要？（考虑 fk = 1/2^k） - amit

无论如何，它都是O(kn)。可能会有更好的限制行为（但实际上没有），但显然它是O(kn)。 - Michael Graczyk

在你的证明中：对于整数分母的最坏情况，我们无法更紧密地限制，因为到k的调和级数的部分和大于log k。但正如amit在开头所说，如果f_k下降得足够快，那么我们可能会得到更好的限制。在序列为1、1/2、1/4、1/8、...的情况下，总操作是O(n)。提问者说每一步的改进是“未知的”，但这可能意味着他不知道而不是不可知，因此实际上可能比O(n log k)更好。正如你所说，根据给定的信息，我们无法证明更好的结果 :-) - Steve Jessop

@SteveJessop我在最后进行了一些手势，因为打字比在纸上写证明更难。然而，“未知”和“不可知”的区别在这里是无关紧要的。为什么呢？OP询问了一个序列1/1、1/f2、1/f3……1/fk，它是非随机的。它们不是随机变量，也不是未确定的。它们是未指定的。未指定的参数不是相同的未知的参数。我的证明是针对任何f1、f2...fk的证明，其中f1>f2>f3>...>fk且0<=f1、f2、...、fk<=1，因为这就是所要求的。没有更多，没有更少。 - Michael Graczyk

这是一个更清晰的例子。我想要证明一个偶数的平方也是偶数。我说，设n是一个偶数。n可以写成2n... 4n.... 4/2...等等QED。在阅读这个证明后，你不会问，“n是未知的还是无法知道的？”它既不是前者也不是后者。它是未指定的，因为它可以是任何整数。这就是关系逻辑的威力，也是证明有效的原因。 - Michael Graczyk