Big-O算法分析
Big-O算法分析
提问于 2012-02-17 16:47:47
我会说这不是家庭作业的问题。这只是一个在线教程资源，用于学习USACO网站上的动态编程概念。在参考资料中，给出了如下问题。
问:一个有多达10000个整数的序列，(0<整数< 100,000)，最大递减子序列是什么？
给出了像样的递归方法。
1 #include <stdio.h>
2 long n, sequence[10000];
3 main () {
4 FILE *in, *out;
5 int i;
6 in = fopen ("input.txt", "r");
7 out = fopen ("output.txt", "w");
8 fscanf(in, "%ld", &n);
9 for (i = 0; i < n; i++) fscanf(in, "%ld", &sequence[i]);
10 fprintf (out, "%d\n", check (0, 0, 99999));
11 exit (0);
12 }
13 check (start, nmatches, smallest) {
14 int better, i, best=nmatches;
15 for (i = start; i < n; i++) {
16 if (sequence[i] < smallest) {
17 better = check (i, nmatches+1, sequence[i]);
18 if (better > best) best = better;
19 }
20 }
21 return best;
22 }伙计们，我不擅长算法分析。你能告诉我在最坏的情况下这个递归枚举解决方案的Big-O符号是什么吗？我个人的想法是O(N^N)，但我没有信心。因为运行时在N <= 100下仍然是可接受的。一定是出了什么问题。请帮帮我。谢谢。
在USACO网站上，它给出了O(n^2)中的动态规划方法，如下所示。
1 #include <stdio.h>
2 #define MAXN 10000
3 main () {
4 long num[MAXN], bestsofar[MAXN];
5 FILE *in, *out;
6 long n, i, j, longest = 0;
7 in = fopen ("input.txt", "r");
8 out = fopen ("output.txt", "w");
9 fscanf(in, "%ld", &n);
10 for (i = 0; i < n; i++) fscanf(in, "%ld", &num[i]);
11 bestsofar[n-1] = 1;
12 for (i = n-1-1; i >= 0; i--) {
13 bestsofar[i] = 1;
14 for (j = i+1; j < n; j++) {
15 if (num[j] < num[i] && bestsofar[j] >= bestsofar[i]) {
16 bestsofar[i] = bestsofar[j] + 1;
17 if (bestsofar[i] > longest) longest = bestsofar[i];
18 }
19 }
20 }
21 fprintf(out, "bestsofar is %d\n", longest);
22 exit(0);
23 }回答 1
Stack Overflow用户
发布于 2012-02-17 17:23:57
只需查看调用函数的参数类型。第一个参数确定第三个参数(顺便说一下，这意味着您需要第三个参数)。第一个范围在0到n之间，第二个比第一个小。这意味着您最多有n^2个不同的函数调用。
现在问题来了，你用相同的参数调用函数多少次。答案很简单:你实际上生成了每个递减的子序列。这意味着对于序列N，N-1，N-2，...您将生成2^N个序列。相当差，对吧(如果你想用我给你的序列做实验)？
但是，如果您使用您应该已经阅读过的memoization技术，则可以将复杂度提高到N^3 (每次调用函数时最多n次操作，不同的调用是N^2，并且memoization只允许您为不同的调用支付一次费用)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/9325251
复制相关文章
相似问题
腾讯云开发者
