4

下面的两个程序从文件中获取 n 个整数，并计算 ath 到 bth 个整数的总和 q（问题数）次。我认为上层程序的时间复杂度比下层程序更差，但是我在计算这两种算法的时间复杂度时遇到了问题。

[input sample]
5 3
5 4 3 2 1
2 3
3 4
2 4

[output sample]
7
5
9

方案一：

#include <stdio.h>

FILE *in=fopen("input.txt","r");
FILE *out=fopen("output.txt","w");

int n,q,a,b,sum;
int data[1000];

int main()
    int i,j;
    fscanf(in,"%d%d",&n,&q);
    for(i=1;i<=n;i++) fscanf(in,"%d",&data[i]);
    for i=0;i<q;i++)
    {
        fscanf(in,"%d%d",&a,&b);
        sum=0;
        for(j=a;j<=b;j++) sum+=data[j];
        fprintf(out,"%d\n",sum);
    }
    return 0;
}

方案二：

#include <stdio.h>

FILE *in=fopen("input.txt","r");
FILE *out=fopen("output.txt","w");

int n,q,a,b;
int data[1000];
int sum[1000];

int main()
{
    int i,j;
    fscanf(in,"%d%d",&n,&q);
    for(i=1;i<=n;i++) fscanf(in,"%d",&data[i]);
    for(i=1;i<=n;i++) sum[i]=sum[i-1]+data[i];
    for(i=0;i<q;i++)
    {
        fscanf(in,"%d%d",&a,&b);
        fprintf(out,"%d\n",sum[b]-sum[a-1]);
    }
    return 0;
}

下面的程序获取从 1 到 m 的 n 个整数并对它们进行排序。同样，我无法计算时间复杂度。

[input sample]
5 5
2 1 3 4 5

[output sample]
1 2 3 4 5

程序：

#include <stdio.h>
FILE *in=fopen("input.txt","r")
FILE *out=fopen("output.txt","w")

int n,m;
int data[1000];
int count[1000];

int main()
{
    int i,j;
    fscanf(in,"%d%d",&n,&m);
    for(i=0;i<n;i++)
    {
        fscanf(in,"%d",&data[i]);
        count[data[i]]++
    }
    for(i=1;i<=m;i++)
    {
        for(j=0;j<count[i];j++) fprintf(out,"%d ",i);
    }
    return 0;
}

具有讽刺意味的是（或不是）我无法计算自己算法的时间复杂度，但我有学习的热情，所以请编程大师帮助我！

4

1 回答 1

3

您需要做的是注意循环，特别是循环重复了多少次，以及在循环内花费了多少时间。您需要将外部循环重复的次数乘以循环内部所花费的时间...如果有内部循环，则将外部循环的重复次数乘以内部循环的重复次数例如，循环以获得时间复杂度。

在您的第一个程序中，您有一个需要 O(n) 时间的循环，然后是一个需要 O(q*(ba)) 时间的循环......我不太清楚 b 和 a 代表什么......但是如果你可以绑定 ba（假设你知道 ba < n），那么你可以更简单地表达这个（例如如果 ba < n，那么你会说它是 O(q*n)）。总运行时间将是这两项的总和，或者，如果一项总是大于另一项，则使用更大的项。

在第二个程序中，您有两个循环，每个循环花费 O(n) 时间，然后是一个花费 O(q) 时间的循环。因此，整体运行时间为 O(n+q)。请注意，如果一个术语支配另一个术语，您可以删除较小的术语。即使不知道 (ba) 的值，也很明显这比第一个要好。

在第三个程序中，总运行时间为 O(n+m)，因为您有一个花费 O(n) 时间的循环，然后是一个花费 O(m) 时间的循环。如果您知道 m < n 或反之亦然，您可以通过删除支配项来简化表达式。如果它们可以变化，以至于您不知道其中一个支配另一个，那么就说明时间复杂度而言，将其写为 O(m+n) 是您可以做的最好的事情。

我还应该指出，即使一个循环执行了不止一次，但它执行了固定次数（例如，在程序 2 中，您有两个循环需要 O(n) 时间），它不会影响时间复杂度，因为 O(2n) 与 O(n) 相同；换句话说，常数因素在大哦复杂性分析中并不重要。此外，如果您的内部循环在执行次数方面有所不同，如果您正在执行“最坏情况”复杂性分析，您只需要知道它可能具有的最差值。

例如，考虑以下循环：

对于 (int i = 0; i < n; i++){
   对于 (int j = i+1; j < n; j++){
       // 花费 O(1) 时间的东西
   }
}

上面的循环需要 O(n^2) 时间，即使并非所有内部循环都需要 O(n) 时间。

我还想补充一点，你应该更好地格式化你的程序。尽管当 if/for/while 语句在主体中只有一个语句时，大括号不是严格要求的，但无论如何使用大括号并使用换行符更具可读性。例如，如果您编写以下代码，则更具可读性：

for (int i=1; i<=n; i++) {
    总和[i]=总和[i-1]+数据[i]；
}

比写成for (i=1; i<=n; i++) sum[i]=sum[i-1]+data[i];. 另外，我应该指出，即使您已将此问题标记为 C++，但您使用的是类似 C 的代码......在 C++ 中，您可以在 for 循环的初始化中声明变量（我建议您这样做）。此外，在 C++ 中，iostreams 库（std::cin、std::cout、std::fstream、std::ostringstream、std::istringstream等）优于 C FILE* 对象。

您可能还对以下资源感兴趣：

于 2010-04-11T12:03:45.617 回答