计算动态数组读取的复杂度

Question

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

如何计算？

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

Answer 1

复杂度为O(元素数量)。

由于在每次迭代中将大小增加了常数因子 2，因此至少一半的元素最多复制一次，四分之一的元素最多复制两次，八分之一的元素最多复制三次，等等。

这意味着复制元素的总数受以下限制

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

乘以元素总数。

如果按常数因子 q 递增，则副本数量将受到 q/(q-1) 的限制，因此该策略始终保证 O(max{初始大小，元素数量}) 复杂度。系数 2 在少量副本(增长因子 q 越大，副本越少)和少量空间开销(如果在上次调整大小后立即停止添加新元素，则有 (q-1)*number_of_elements 未使用的空间)。