0

目標：文字列と2つの長さへのポインタを受け取り、入力のサイズに依存する追加のメモリを使用せずに、長さで表される内側の文字列を交換する関数。たとえば、文字列「abcdef123」と長さが6,3の場合、結果は「123abcdef」になります。

考えられる再帰的な実装（私のもの）の1つは次のとおりです。

void invertStrings(char* str, int len1, int len2){
    if(len1==0 || len2==0)
        return;
    if(len1>len2){
        for(int i=0;i<len2;++i)
            swapChars(str, len1+i, len1-len2+i);
        invertStrings(str,len1-len2,len2);
    }
    else{
        for(int i=0;i<len1;++i)
            swapChars(str, len1+i, i);
        invertStrings(str+len1,len1,len2-len1);
    }
}

時間計算量はO（len1 + len2）か、O（max {len1、len2}）のようなものだと思います。

質問：時間計算量とは何ですか？それをどのように証明できますか？ありがとう。

4

2 に答える 2

3

書かれているアルゴリズムはのようですO(len1+len2)。関数呼び出しの「総作業量」をとして定義しましょうlen1 + len2。関数が呼び出されるたびに、関数はmin(len1,len2)スワップを実行し、を使用して再帰的に呼び出しますtotal_work[n+1] = total_work[n] - min(len1,len2)。したがって、すべての再帰呼び出しで実行される作業の上限は、ですlen1+len2。

ここでの追加のねじれは、終了条件がに依存することgcd(len1,len2)です。len1、len2のいずれかが0になるとループが終了するため、スワップの数が厳密に。未満であることが保証されますlen1+len2。最後に「残り」がいくらになるかは、2つの長さのgcdによって異なります。例(6,3)として、開始点として持っている場合(6,3)->(3,3)->(0,3)、合計6つのスワップ（予想される8つ未満）に対して、を取得します。しかし、最初は(7,3)->(4,3)->(1,3)->(1,2)->(1,1)->(1,0)9回のスワップを行うことになります。一般的なスワップの数は正確にlen1 + len2 - gcd(len1,len2)です。

于 2012-12-31T15:49:49.080 に答える
0

すべてのスワップ操作で少なくとも1つの文字が正しい最終位置に配置されるため、これはO（n）です。

アルゴリズムの複雑さは入力のサイズの関数であり、ここでは操作のコストは入力のサイズに比例して増加します。

通常、複雑さを伴うため、それが示す成長のタイプのみを気にします。線形の場合、係数が何であるかは関係ありません（たとえば、入力データの量の2倍または7であるかどうかは関係ありません）。

于 2012-12-31T15:12:42.393 に答える