4

The two programs below get n integers from file and calculates the sum of ath to bth integers q(number of question) times. I think the upper program has worse time complexity than the lower, but I'm having problems calculating the time complexity of these two algorithms.

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

[output sample]
7
5
9

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

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

The programs below gets n integers from 1 to m and sorts them. Again, I cannot calculate the time complexity.

[input sample]
5 5
2 1 3 4 5

[output sample]
1 2 3 4 5

Program:

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

It's ironic(or not) that I cannot calculate the time complexity of my own algorithms, but I have passions to learn, so please programming gurus, help me!

4

1 に答える 1

3

ループに注意を払う必要があります。具体的には、ループが繰り返される回数と、ループ内で費やされる時間です。外側のループが繰り返される回数に、ループ内でかかる時間を掛ける必要があります...内側のループがある場合は、外側のループの繰り返し回数に内側の繰り返し回数を掛けます。たとえば、ループして時間の複雑さを取得します。

最初のプログラムでは、O(n) 時間かかるループが 1 つあり、その後に O(q*(ba)) 時間かかるループがあります... b と a が何を表しているのか正確にはわかりません...しかし、ba をバインドできる場合 (たとえば、ba < n であることがわかっている場合)、これをより簡単に表現できます (たとえば、ba < n の場合、O(q*n) であると言えます)。全体の実行時間は、これら 2 つの項の合計になります。または、一方の項が常に他方よりも大きい場合は、大きい方の項を使用します。

2 番目のプログラムには、それぞれ O(n) 時間かかる 2 つのループがあり、その後に O(q) 時間かかるループが続きます。したがって、全体の実行時間は O(n+q) です。1 つの用語が他の用語を支配する場合は、小さい方の用語を削除できることに注意してください。(ba) の値を知らなくても、これが最初のものより優れていることは明らかです。

3 番目のプログラムでは、O(n) 時間かかるループが 1 つあり、その後に O(m) 時間かかるループがあるため、全体の実行時間は O(n+m) です。m < n またはその逆であることがわかっている場合は、主項を削除して式を単純化できます。それらが変化する可能性があるため、一方が他方を支配していることがわからない場合は、時間の複雑さを述べるという点で、O(m+n) として書き出すことが最善です。

また、ループが複数回実行されたとしても、一定の回数実行されたとしても (たとえば、プログラム 2 では、O(n) 時間かかる 2 つのループがあります)、ループには影響しません。 O(2n) は O(n) と同じであるため、時間の複雑さ。言い換えれば、大きな複雑さの分析では、一定の要因は重要ではありません。また、実行回数が変化する内部ループがある場合、「最悪の場合」の複雑さの分析を実行している場合は、可能な限り最悪の値を知るだけで済みます。

たとえば、次のループを考えてみましょう。

for (int i = 0; i < n; i++ ){
   for (int j = i+1; j < n; j++ ){
       // O(1) 時間かかるもの
   }
}

すべての内側のループが O(n) 時間かかるわけではありませんが、上記のループは O(n^2) 時間かかります。

また、プログラムのフォーマットをより適切に行う必要があることも付け加えておきます。if/for/while ステートメントの本体にステートメントが 1 つしかない場合、中かっこは厳密には必要ありませんが、とにかく中かっこを使用し、改行を使用する方がはるかに読みやすくなります。たとえば、次のように書くと、はるかに読みやすくなります。

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++ では、 C FILE* オブジェクトよりもiostream ライブラリ( std::cin、std::cout、std::fstream、std::ostringstream、std::istringstreamなど) が優先されます。

次のリソースにも興味があるかもしれません。

于 2010-04-11T12:03:45.617 に答える