-1

有人知道这个读取动态整数数组的函数的复杂性是什么，当没有足够的空间容纳下一个输入时，它会将数组大小加倍并将其复制到新的更大数组（内存中的地址）中？

我该如何计算呢？

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/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. 由于您的分配大小每次都会翻倍，因此如果您读取 n 个元素，您会分配 lg(n) 次。

  2. 在每次分配时，您复制了所有已读取的元素，即上次 n 次复制，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. 用 lg(n) 替换 m，即 2^(lg(n) + lg(2)) = 2^(lg(2n)) = 2n，因此复杂度，就你做了多少份而言，是 O( n)。

于 2012-12-28T17:25:24.983 回答