algorithm - Big-O算法分析

Question

我想说这不是作业问题。它只是 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  }

Answer 1

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

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

但是，如果您使用您应该已经阅读过的内存技术，您可以将复杂度提高到 N^3 (每次调用函数时最多执行 n 个操作，不同的调用是 N^2 并且内存允许您对于不同的调用只需支付一次)。