排序算法的时间复杂度

Question

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

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

[output sample]
7
5
9

程序 1：

#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;
}

程序 2：

#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;
}

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

Answer 1

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

在你的第一个程序中，你有一个需要 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 <反之亦然，您可以通过删除主导项来简化表达式。如果它们可以变化，以至于您不知道其中一个支配另一个，那么就说明时间复杂度而言，将其写为 O(m+n) 是最好的选择。

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

例如，考虑以下循环：

for (int i = 0; i < n; i++ ){
   for (int j = i+1; j < n; j++ ){
       // something taking O(1) time
   }
}

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

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

for (int i=1; i<=n; i++) {
    sum[i]=sum[i-1]+data[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, < a href="http://www.cplusplus.com/reference/iostream/istringstream/" rel="nofollow noreferrer">std::istringstream 等）优于 C FILE* 对象。

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

• 斯坦福大学：算法分析 来自 Google 代码大学