4

我有一个迭代算法，在每次迭代中，计算量逐渐减少。这是我的算法的说明：

Input size: n和Total iteration = 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)

Update:

我认为这个问题似乎很模糊。我会用文字来解释：

我的算法的输入是n，我将在k迭代中运行它。但在每次迭代中，输入大小都会减少一个因子，即unknown. 减少没有模式。

例如：

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)
4

2 回答 2

3

给定的信息是不够的，我们只能确定复杂度为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值可以给出不同的严格界限。

于 2012-07-16T10:49:50.850 回答
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)

是严格的整数，那么它是O(n*log k )。

这就是为什么。要使序列 Xn 为O(Yn)，必须存在一些 M（实数）和 m（整数），使得 Xn < M*|Yn| 对于所有 n > m。

现在考虑序列 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)。

于 2012-07-16T10:49:19.200 回答