我得到了这个函数，想知道时间复杂度：
int f2(int n) {
if(n<2) return 1;
return f2(n/2)+f2(n-2);
}
我使用伸缩膨胀法计算了它的运行时间为 O(n 2 )。这个对吗？
编辑：重新考虑后，我发现这个函数的结构与mergesort相似，复杂度为Θ(n log n)。那是对的吗？
问问题
1981 次
6 回答
3
假设它是 n 中的多项式，即对于某些常数和，运行时间 T(n) 至多为 a*n b。然后，我们有：ab
T(n) = T(n/2) + T(n-2)
= a*(n/2)^b + a*(n-2)^b
= a/2^b * n^b + a*n^b + (lower-order terms)
= a*n^b * (1/2^b + 1) + (lower-order terms)
其中(lower-order terms)由 和 和 差的n提高到 权力 严格 小于b. 对于足够大n的 ， a*n b * (1/2 b + 1) 项将主导低阶项，并且始终大于 a*n b，因此 T(n) 不是 O (n b ) 对于任何常数b。
现在假设它在 n 中是指数的，即对于某些常数和，T(n) 至多是 a*b n。然后：ab
T(n) = T(n/2) + T(n-2)
= a*b^(n/2) + a*b^(n-2)
= a*b^n * (b^(-n/2) + 1/b^2)
现在如果 b > 1 且 n >= -2 log(1 - 1/b 2 ) / log(b)，则：
n >= -2 log(1 - 1/b^2) / log(b)
-n/2 <= log(1 - 1/b^2) / log(b) = log_b(1 - 1/b^2)
b^(-n/2) <= 1 - 1/b^2
b^(-n/2) + 1/b^2 <= 1
T(n) = a*b^n * (b^(-n/2) + 1/b^2) <= a*b^n * 1 = a*b^n
因此，对于任何 a > 0 和 b > 1，存在一个 N（等于 -2 log(1 - 1/b 2 ) / log(b)），使得对于所有 n >= N，T(n) < = a*b^n。
那么这说明了什么？T(n) 大于多项式（对于任何多项式；还包括多项式函数，例如任何多项式函数都是 o（更大的非对数多项式）），但 T(n) 小于任何指数。我不确定是否有确切结果的简单公式，但这些是一些有用的界限。
编辑
正如 nhahtdh 指出的那样，这使得运行时间称为准多项式时间。
于 2013-09-18T05:31:27.253 回答
1
TL;DR：我认为递归是 n O(log n)，这是超多项式但次指数。我没有匹配的下限，我怀疑这很严格，但这是进步！
我想我可以得到一个次指数但超多项式的上限。结合@Adam Rosenfield 的回答表明没有多项式界限，这表明
- 递归没有多项式界限，但
- 任何指数界都必须是弱的。
我们要解决的递归是
T(n) = T(n - 2) + T(n / 2) + 1
T(1) = T(2) = 1
我的一个想法是，我们可能能够以特定的顺序评估这种重复。假设您要评估 T(n)。这样做一步会产生
T(n - 2) + T(n / 2) + 1
现在，假设我们展开 T(n - 2) 项。这给
T(n - 4) + T(n / 2 - 1) + T(n / 2) + 2
现在，展开 n - 4 项。这样做会给
T(n - 6) + T(n / 2 - 2) + T(n / 2 - 1) + T(n / 2) + 3
我们可以一遍又一遍地重复扩展减法项（形式为 T(n - 2k) 的项）的过程。那么，如果我们将它扩展到 n - 2k 大约为 n / 2 的程度会发生什么？这将发生大约 n / 4 次。如果我们这样做，我们会得到那个
T(n) = T(n / 2) + T(n / 2) + T(n / 2 - 1) + T(n / 2 - 2) + ... + T(n / 2 - n / 4 ) + n / 4
我将假设 T(n) 是非递减的。如果我们这样做，我们会得到那个
T(n) ≤ T(n / 2) + T(n / 2) + T(n / 2) + ... + T(n / 2) + n / 4
T(n) ≤ (n / 4 + 1) T(n / 2) + n / 4
我将在这里的数学有点粗糙，并进行另一个简化：不是让 T(n / 2) 的系数为 (n / 4 + 1)，而是让它为 n / 4. 我知道这不安全，但我推测它不会对结果造成太大影响。不过，最好仔细检查其余部分是否仍然有效！
这意味着我们可以（大致）简化上面的递归来得到
T(n) ≤ (n / 4) T(n / 2) + n / 4
这更容易处理，我们现在可以尝试直接解决它。我们将使用迭代方法，并一遍又一遍地将其插入自身，直到我们发现一个模式。如果我们这样做，我们会看到以下模式：
T(n) ≤ (n / 4) T(n / 2) + n / 4
≤ (n / 4)((n / 8) T(n / 4) + n / 8) + n / 4
= (n 2 / 32) T(n / 4) + n / 4 + n 2 / 32
≤ (n 2 / 32) ((n / 16) T(n / 8) + n / 16) + n / 4 + n 2 / 32
= (n 3 / 512) T(n / 8) + n / 4 + n 2 / 32 + n 3 / 512
≤ (n 3 / 512) ((n / 32) T(n / 16) + n / 32) + n / 4 + n 2 / 32 + n 3 / 512
= (n 4 / 16384) T(n / 16) + n / 4 + n 2 / 32 + n 3 / 512 + n 4 / 16384
让我们看看正在出现的模式。在这样做 k 次之后，T(n / 2 k )的系数是 n k除以 2 的某个幂。到目前为止，2 的幂是 4、32、512、16384。这些数字似乎没有任何明显的模式，但如果我们将它们重写为 2 2、2 5、2 9、2 14我们看到它们遵循模式 0, 2, 5, 9, 14, ... 。这比三角形数 1, 3, 6, 10, 15, ... 小一。这不是巧合：如果你仔细想想，每次我们展开递归式时，分母都会不断地乘以 2 的下一个幂，这会将 2 的幂的指数从一个三角形数增加到下一个三角形数。因此，我们期望 k 次迭代后的分母由下式给出
2 (k + 1)(k + 2) / 2 - 1
之后，剩下的项是 n 的幂的总和除以 2 的幂到各种三角数。因此，如果我们将事物扩展 k 次，我们得到
T(n) ≤ (n k / 2 (k + 1)(k + 2) / 2 - 1 ) T(n / 2 k ) + Σ i = 0 k (n i / 2 (i + 1)(i + 2) / 2 - 1 )
好的！所以这是一团糟，但并不是那么糟糕。我们知道递归在 n / 2 k = 1 时立即停止，这发生在 k = lg n 时。为了使事情更简单，我将更改基本情况，以便在 n / 2 k = 2 时停止递归，这发生在 k = lg n - 1 时。这不会改变任何东西超过一个常数因素。因此，如果我们将 k = lg n - 1 代入上述公式，我们可以化简为上界的闭式表达式。这样做会得到以下结果：
T(n) ≤ (n k / 2 (k + 1)(k + 2) / 2 - 1 ) T(n / 2 k ) + Σ i = 0 k (n i / 2 (i + 1)(i + 2) / 2 - 1 )
= (n lg n - 1 / 2 (lg n)(lg n + 1) / 2 - 1 ) T(2) + Σ i = 0 lg n - 1 (n i / 2 (i + 1)(i + 2) / 2 - 1 )
哦，那不漂亮。然而，它并没有看起来那么糟糕。让我们看一下第一项的分母：
2 (lg n)(lg n + 1) / 2 - 1
使用指数的基本定律，我们得到
2 (lg n)(lg n + 1) / 2 - 1
= (2 lg n ) (lg n + 1) / 2 - 1
= n (lg n + 1) / 2 - 1
那还不错！因此，如果我们采用表达式
n lg n - 1 / 2 (lg n)(lg n + 1) / 2 - 1
我们看到它简化如下：
n lg n - 1 / 2 (lg n)(lg n + 1) / 2 - 1
= n lg n - 1 / n (lg n + 1) / 2 - 1
= n (lg n - 1 - ((lg n + 1) / 2 - 1))
= n (lg n - (lg n + 1) / 2)
= n (2 lg n - lg n - 1) / 2)
= n (lg n - 1) / 2)
= n O(lg n)
漂亮！那个主导词最终的形式是 n O(lg n)！
那么剩下的呢？好吧，我们有这个可怕的总结要对付：
Σ i = 0 lg n - 1 (n i / 2 (i + 1)(i + 2) / 2 - 1 )
幸运的是，我们可以注意到的一件事是
n i / 2 (i + 1)(i + 2) / 2 - 1
≤ n i / 2 (i + 1)(i + 2)
≤ n i / 2 (i + 1)
≤ n i / 2 i
= (n / 2)我
因此，如果我们想要做的只是求和的上限，我们可以使用这个更简单的求和来实现：
Σ i = 0 lg n - 1 (n / 2) i
由于 n / 2 > 0，这个和的上限依次为
Σ i = 0 lg n - 1 (n / 2) lg n - 1
= (lg n)(n lg n - 1 ) / (2 lg n - 1 )
= (2 lg n)(n lg n - 1 ) / n
= (2 lg n)n lg n - 2
= n O(lg n)
还有宾果游戏，这个可怕的总和的第二项也是 n O(lg n)！这意味着我们有T(n) = n O(log n)。这个界限不一定很紧，但它确实表明递归绝对是次指数的，因为 n O(log n)比任何指数函数增长得更慢！
希望这可以帮助！
于 2013-09-18T07:39:35.857 回答
0
于 2013-09-17T17:49:49.793 回答
0
T(n) = T(n/2) + T(n-2) + 1
我们知道 T(n-2) > T(n/2)
我们可以说：
T(n) = 2T(n-2) + 1
所以 T(n-2) = 2T(n-4) + 1
T(n) = 4T(n-4) + 2
T(n) = 8T(n-6) + 3
T(n) = (2^k)T(n-2k) + k
因为我们知道 T(1) = 1
那么 n-2k = 1 -> k = (n-1)/2
T(n) = 2^((n-1)/2)T(1) + (n-1)/2
T(n) = 2^((n-1)/2) + (n-1)/2
T(n) = 2^((n-1)/2)
不过一定有更好的解决方案。
于 2013-09-17T19:56:31.693 回答
0
总是有经验的方法 - 时间它......
#include "timer.h"
#include <stdio.h>
static
int f2(int n)
{
if (n < 2)
return 1;
return f2(n/2) + f2(n-2);
}
int main(void)
{
printf("Fast:\n");
for (int i = 1; i <= 512; i *= 2)
{
Clock clk;
clk_init(&clk);
clk_start(&clk);
long sum = 0;
for (int j = 0; j < 100; j++)
sum += f2(i);
clk_stop(&clk);
char buffer[32];
printf("%8d: elapsed %10s s; sum = %12ld\n",
i, clk_elapsed_us(&clk, buffer, sizeof(buffer)), sum/100);
}
printf("\nSlow:\n");
for (int i = 512; i < 1024; i += 16)
{
Clock clk;
clk_init(&clk);
clk_start(&clk);
long sum = 0;
for (int j = 0; j < 100; j++)
sum += f2(i);
clk_stop(&clk);
char buffer[32];
printf("%8d: elapsed %7s s; sum = %12ld\n",
i, clk_elapsed_ms(&clk, buffer, sizeof(buffer)), sum/100);
}
return 0;
}
结果：
作为记录，测试是在运行 Mac OS X 10.8.5、2.3 GHz 的 Intel Core i7 和 16 GiB RAM 的 MacBook Pro 上运行的。
Fast:
1: elapsed 0.000000 s; sum = 1
2: elapsed 0.000001 s; sum = 2
4: elapsed 0.000001 s; sum = 4
8: elapsed 0.000002 s; sum = 10
16: elapsed 0.000008 s; sum = 36
32: elapsed 0.000045 s; sum = 202
64: elapsed 0.000408 s; sum = 1828
128: elapsed 0.005985 s; sum = 27338
256: elapsed 0.139971 s; sum = 692004
512: elapsed 5.273834 s; sum = 30251722
Slow:
512: elapsed 5.286 s; sum = 30251722
528: elapsed 6.370 s; sum = 36243644
544: elapsed 7.609 s; sum = 43234278
560: elapsed 8.949 s; sum = 51361196
576: elapsed 10.397 s; sum = 60777212
592: elapsed 12.171 s; sum = 71651844
608: elapsed 14.394 s; sum = 84172786
624: elapsed 16.716 s; sum = 98547380
640: elapsed 19.176 s; sum = 115004102
656: elapsed 21.985 s; sum = 133794468
672: elapsed 25.295 s; sum = 155194954
688: elapsed 29.170 s; sum = 179508916
704: elapsed 33.456 s; sum = 207068524
720: elapsed 38.317 s; sum = 238237116
736: elapsed 43.776 s; sum = 273411566
752: elapsed 49.878 s; sum = 313024652
768: elapsed 56.979 s; sum = 357547444
784: elapsed 64.456 s; sum = 407492292
800: elapsed 72.980 s; sum = 463415834
816: elapsed 82.535 s; sum = 525922004
832: elapsed 93.062 s; sum = 595665060
848: elapsed 104.886 s; sum = 673353212
864: elapsed 118.038 s; sum = 759752270
880: elapsed 132.569 s; sum = 855689292
896: elapsed 150.487 s; sum = 962056258
912: elapsed 166.065 s; sum = 1079814524
928: elapsed 185.616 s; sum = 1209999302
944: elapsed 206.875 s; sum = 1353724140
960: elapsed 230.670 s; sum = 1512185428
976: elapsed 256.718 s; sum = 1686667684
992: elapsed 285.158 s; sum = 1878548866
1008: elapsed 316.281 s; sum = 2089305684
我没有曲线拟合该数据。显然，您可以减少或消除较大尺寸的迭代，依此类推（这将避免 1024 发生的溢出，等等）。
如果有人在绘制图表方面有一定的专业知识，它可能会显示结果（当时的对数刻度）。
于 2013-09-18T13:12:30.290 回答
-1
于 2013-09-17T17:25:44.857 回答