0

所以我push_back为向量类编写了一个函数，现在我正在尝试计算摊销时间复杂度。我对编程的理论方面还很陌生，所以如果有人能引导我完成它，那就太棒了。

这是我的功能：

void Vector<T>::push_back(const T &e) {
    if(vsize + 1 > capacity)
        allocate_new();
    array[vsize] = e;
    vsize++;
}

这是我的allocate_new功能：

void Vector<T>::allocate_new() {
    capacity = vsize * 4;
    T* tmp = new T[capacity];

    for(int i = 0; i < vsize; i++)
        tmp[i] = array[i];

    delete[] array;
    array = tmp;
}
4

2 回答 2

1

当您将N元素插入数组时，数组必须以 4 的每个幂调整大小。调整大小所需的时间4^i为O(4^i). 同样，最大调整大小是在 size 完成的N。所以总金额为：

T = 1 + 4 + 16 + ... + 4^x

哪里4^x <= N。因此T=O(4^x)=O(N)。因此，每个插入操作的平均时间是 on O(1)。

于 2013-09-30T23:33:05.990 回答
1

简短的回答是，随着存储空间变大，复制所需的时间是原来的 4 倍，但发生的频率只有原来的1/4 。4 和 1/4取消，所以你最终得到（摊销的）恒定时间。

忽略您选择的精确因素，从长远来看，您会得到 O(N * 1/N) = O(1) -> 摊销常数时间。

于 2013-09-30T23:34:01.587 回答