尋找分期時間複雜度

所以我寫了一個矢量類的函數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; 
}

來源

2013-09-30 Connor Black

這可能更適合[cs.se]。 – millimoose

是的，在這裏回答：http://cs.stackexchange.com/questions/9380/why-is-push-back-in-c-vectors-constant-amortized – rileyberton

簡短的回答是，隨着存儲空間變大，副本需要4倍的時間，但是經常會發生1/4 ^th。 4和1/4將取消，所以最終（攤銷）時間不變。

忽略你選擇的確切因素，從長期來看，你會得到O（N * 1/N）= O（1） - >攤銷常量時間。

來源

2013-09-30 23:34:01

當你插入N元素融入到陣列，該陣列具有在4每個功率來調整。調整尺寸爲4^i的時間量爲O(4^i)。同樣，最大尺寸調整大小爲N。所以採取的總量爲：

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

其中4^x <= N。因此T=O(4^x)=O(N)。因此每個插入操作的平均時間爲O(1)。

來源

2013-09-30 23:33:05 tskuzzy

尋找分期時間複雜度

回答

相關問題