1

したがって、次のコードがあり、実行時間の増加率を導出する必要がありますが、どこから始めればよいかわかりません。私の質問は、どうすればこれを行うことができますか? どんな助けでも大歓迎です。

ありがとうございました。

// function to merge two sorted arrays
int merge (int smax, char sArray[], int tmax, char tArray[], char target[])
{
    int m, s, t;
    for (m = s = t = 0; s < smax && t < tmax;  m++)     
    {
        if (sArray[s] <= tArray[t]) 
        {
            target[m] = sArray[s];
            s++;
        }
        else
        {
            target[m] = tArray[t];
            t++;
        }
    }
    int compCount = m;
    for (; s < smax; m++)
    {
        target[m] = sArray[s++];
    }
    for (; t < tmax; m++)
    {
        target[m] = tArray[t++];
    }
    return compCount;
}
4

2 に答える 2

0

すべてのループは、反復回数が (smax + tmax) で制限されます。したがって、アルゴリズムはO( max(smax,tmax) )またはであると言えますO( smax +tmax)

于 2012-07-05T12:15:43.513 に答える
0

それは実際には非常に簡単です。

ほら、最初のforループは反復ごとにまたは のいずれsかで増加するので、です。2 番目のループは明らかにで、3 番目のループは です。全体として、 が得られます。tO(smax + tmax)O(smax)O(tmax)O(smax + tmax)

(もっと巧妙な証明方法がいくつかありますが、意図的に省略しています。)

于 2012-07-05T12:15:14.157 に答える