-1

整数の動的配列を読み取るこの関数の複雑さを誰かが知っていますか？次の入力のための十分なスペースがない場合、配列サイズを2倍にして、新しい大きな配列（メモリ内のアドレス）にコピーしますか？

どうすれば計算できますか？

void readDynamicArray(int* arr, int& physicalSize, int& logicalSize)
{
    physicalSize=2;
    arr= new int[physicalSize];

    int tmpNum;
    logicalSize=0;
    cin>>tmpNum;

    while (tmpNum!=-1)// stop sign is -1, will help know when to stop reading into the array
    {
        if (logicalSize==physicalSize)
        {
            arr=newArrLoc(arr, physicalSize, logicalSize);
        }
        arr[logicalSize]=tmpNum;
        logicalSize++;
        cin>>tmpNum;
    }
}

int* newArrLoc(int* arr, int& physicalSize, int logicalSize)
{
    int* newArr=new int[physicalSize*=2];
    copyArray(newArr, arr, logicalSize);
    delete[] arr;   
    return newArr;
}

void copyArray (int arr[],int srcArr[] ,int size)
{
    int i;
    for (i=0;i<size;i++)
    {
        arr[i]=srcArr[i];
    }
}
4

2 に答える 2

1

複雑さはO(number of elements).

各反復でサイズを一定の係数 2 で増やすため、要素の少なくとも半分は最大で 1 回、4 分の 1 は最大で 2 回、8 分の 1 は最大で 3 回コピーされます。

つまり、コピーされた要素の総数は次のように制限されます

1/2 + 2/2^2 + 3/2^3 + 4/2^4 + ... = 2

要素の総数の倍。

一定の係数qでインクリメントすると、コピーの数は で制限されるq/(q-1)ため、戦略は常にO(max{initial size, number of elements})複雑さを保証します。係数 2 は、少数のコピー (増加係数が大きくなるほどコピーqが少なくなる) と小さなスペース オーバーヘッド (最後のサイズ変更の直後に新しい要素の追加を停止すると、(q-1)*number_of_elementsスペースが未使用になる) の間の適切な妥協点になります。

于 2012-12-28T17:01:49.257 に答える
0

  1. 割り当てのサイズは毎回 2 倍になるため、n 要素を読み取ると、割り当てを lg(n) 回行ったことになります。

  2. 各割り当てで、既に読み取られたすべての要素をコピーしました。つまり、前回 n コピー、最後から 2 番目から n/2 コピー、などです。したがって、合計コピーは Sum(2 + 2^2 + 2^3 + ... + n) であり、その中に lg(n) 項があります。

  3. n が 2 のべき乗であり、m = lg(n) であると仮定すると、合計は Sum(i from 0 to m) (2^i) となり、2^(m+1) で制限されます。

  4. m を lg(n) に置き換えます。これは 2^(lg(n) + lg(2)) = 2^(lg(2n)) = 2n なので、作成したコピーの数に関する複雑さは O( n)。

于 2012-12-28T17:25:24.983 に答える