在vs下,vector 在插入新的元素時,如果容量已滿的時候需要擴容為原容量的1.5倍
如果擴容是個常量(M),即下次擴容的容量為上次的M+K,若***有N個元素需要添加進vector(push_back)
則***需要N/M次擴容,若第壹次容量為1,下壹次1+M時需要復制1次,再下壹次1+M```,1+KM(>=N)
則添加N個元素需要時間復雜度:
平均時間復雜度為O(N)
如果擴容量是倍數(M),級下次擴容的容量為上次的MK,同理,***需要 次,若第壹次容量為1,下壹次擴容為M時需要復制1次,再下壹次M次···,M K (>=N)
則添加N個元素需要時間復雜度:
平均時間復雜度為O(1)
對於增長的倍數,壹般不大於2,因為若倍數為2,參考如下分配:
由於兩倍擴容,因此每次都是正好比上壹次分配的空間大,因此之前分配的空間無法再復用
而若是1.5倍,同樣的例子:
可知,經歷了幾次擴容,之前的空間可以復用