gpt4 book ai didi

algorithm - 大O算法分析

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:44:49 25 4
gpt4 key购买 nike

我会说这不是作业问题。它只是一个在线教程资源,用于从 USACO 网站学习动态编程概念。在资源中,给出了如下问题。

问题: 一个多达10000个整数的sequcen,(0 < integer < 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下runtime还是可以接受的。一定是哪里出了问题。请帮我。谢谢。

在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 }

最佳答案

只要看看你用什么样的参数调用这个函数。第一个决定第三个(顺便说一句,这意味着你需要第三个参数)。第一个范围介于 0 和 n 之间。第二个比第一个小。这意味着您最多对该函数有 n^2 次不同的调用。

现在问题来了,你用相同的参数调用了多少次函数。答案很简单:你实际上生成了每一个递减的子序列。这意味着对于序列 N, N-1, N-2, ... 您将生成 2^N 个序列。很差,对吧(如果你想用我给你的序列做实验)?

然而,如果你使用你应该已经读过的内存技术,你可以将复杂度提高到 N^3(每次调用函数最多 n 次操作,不同的调用是 N^2,内存允许你只需为不同的电话支付一次)。

关于algorithm - 大O算法分析,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9325251/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com