O(size(vector)), but also we know t

O(size(vector)), but also we know that the latter case occurs only occasionally and leads to doubling the size of the vector. In this case, what is the expected efficiency of one insertion in the series of insertions? Note that we are interested only in sequences of insertions, excluding deletions and modifications, to have the worst case scenario. The outcome of amortized analysis depends on the assumed amortized cost of one insertion. It is clear that if
amCost(push(x)) = 1
where 1 represents the cost of one insertion, then we are not gaining anything from this analysis because easy insertions are paying for themselves right away, and the in- sertions causing overflow and thus copying have no credit to use to make up for their high cost. Is
amCost(push(x)) = 2
a reasonable choice? Consider the table in Figure 2.6a. It shows the change in vector capacity and the cost of insertion when size grows from 0 to 18; that is, the table in- dicates the changes in the vector during the sequence of 18 insertions into an initially empty vector. For example, if there are four elements in the vector (size = 4), then

ผลลัพธ์ (ไทย) 1:

O(size(vector)) แต่เราทราบว่า กรณีหลังเกิดขึ้นบ่อย และให้จะขนาดของเวกเตอร์ ในกรณีนี้ คืออะไรแทรกหนึ่งในชุดของแทรกประสิทธิภาพที่คาดไว้หรือไม่ หมายเหตุว่า เราสนใจเฉพาะในลำดับของแทรก ไม่รวมการลบและการปรับเปลี่ยน มีสถานการณ์กรณีเลวร้ายที่สุด ผลลัพธ์ของการวิเคราะห์ซึ่งตัดจำหน่ายขึ้นอยู่กับการปลอมซึ่งตัดจำหน่ายต้นทุนหนึ่งแทรก ก็ชัดเจนว่าถ้าamCost(push(x)) = 1ที่ 1 แสดงต้นทุนของแทรกหนึ่ง แล้วเราจะไม่ได้รับอะไรจากการวิเคราะห์นี้ เพราะแทรกง่ายจะจ่ายสำหรับตัวเองทันที และที่ใน-sertions ให้เกิดมากเกินไป และการคัดลอกดังนั้น มีเครดิตไม่ใช้เพื่อให้ค่าของต้นทุนที่สูง มีamCost(push(x)) = 2ทางเลือกที่เหมาะสมหรือไม่ พิจารณาตารางในรูป 2.6a จะแสดงการเปลี่ยนแปลงในเวกเตอร์ผลิตและต้นทุนของแทรกเมื่อขนาดขยาย 0 18 นั่นคือ การตารางใน-dicates การเปลี่ยนแปลงในเวกเตอร์ระหว่างลำดับของแทรก 18 เป็นเวกเตอร์เริ่มว่าง ตัวอย่างเช่น ถ้ามีธาตุทั้งสี่ในเวกเตอร์ (ขนาด = 4), จากนั้น

ผลลัพธ์ (ไทย) 2:

O (ขนาด (เวกเตอร์)) แต่ยังเรารู้ว่ากรณีหลังเกิดขึ้นเป็นครั้งคราวเท่านั้นและนำไปสู่การเพิ่มขนาดของเวกเตอร์ ในกรณีนี้สิ่งที่เป็นประสิทธิภาพที่คาดหวังของการแทรกหนึ่งในชุดของการแทรกหรือไม่ โปรดทราบว่าเรามีความสนใจเฉพาะในลำดับของการแทรกไม่รวมการลบและการปรับเปลี่ยนเพื่อให้มีสถานการณ์กรณีที่เลวร้ายที่สุด ผลของการวิเคราะห์ตัดจำหน่ายขึ้นอยู่กับค่าใช้จ่ายตัดจ่ายสันนิษฐานหนึ่งแทรก เป็นที่ชัดเจนว่าถ้า
amCost (การผลักดัน (x)) = 1
ที่ 1 แสดงให้เห็นถึงค่าใช้จ่ายของหนึ่งแทรกแล้วเราจะไม่ได้รับความอะไรจากการวิเคราะห์นี้เพราะการแทรกง่ายจะจ่ายสำหรับตัวเองทันทีและ sertions หก่อให้เกิดการล้นและ จึงมีการคัดลอกไม่มีเครดิตเพื่อใช้ในการทำขึ้นสำหรับค่าใช้จ่ายสูงของพวกเขา เป็น
amCost (การผลักดัน (x)) = 2
เป็นทางเลือกที่เหมาะสม? พิจารณาตารางในรูปที่ 2.6a มันแสดงให้เห็นการเปลี่ยนแปลงในความสามารถเวกเตอร์และค่าใช้จ่ายของการแทรกเมื่อขนาดเติบโต 0-18 นั้น ว่ามีโต๊ะห dicates การเปลี่ยนแปลงในเวกเตอร์ในช่วง 18 ลำดับของการแทรกลงในเวกเตอร์ที่ว่างเปล่าในขั้นต้น ตัวอย่างเช่นถ้ามีธาตุทั้งสี่ในเวกเตอร์ (ขนาด = 4) แล้ว

ผลลัพธ์ (ไทย) 3:

O ( ขนาด ( เวกเตอร์ ) ) แต่เรายังทราบว่า กรณีหลังเกิดขึ้นเป็นครั้งคราว และนำไปสู่การเพิ่มขนาดของเวกเตอร์ ในกรณีนี้คือสิ่งที่คาดหวังประสิทธิภาพหนึ่งแทรกในชุดใหม่ ? ทราบว่าเราสนใจเฉพาะในลำดับใหม่ ยกเว้นลบและปรับเปลี่ยนเพื่อให้มีสถานการณ์สมมติกรณีเลวร้ายที่สุดผลที่ได้จากการวิเคราะห์ว่า ของขวัญของขวัญ ขึ้นอยู่กับต้นทุนของการแทรก มันเป็นที่ชัดเจนว่าถ้า
amcost ( กด ( X ) = 1
ที่ 1 แสดงถึงค่าใช้จ่ายของหนึ่งแทรก เราก็จะไม่ได้รับอะไรจากการวิเคราะห์นี้จะจ่ายสำหรับตัวเองเพราะแทรกได้ง่ายทันที และใน sertions ก่อให้เกิดล้นจึงคัดลอกไม่มีเครดิตที่จะใช้เพื่อชดเชยต้นทุน สูงของพวกเขาคือ
amcost ( กด ( X ) = 2
เป็นทางเลือกที่เหมาะสม ? พิจารณาตารางในรูป 2.6a มันแสดงให้เห็นการเปลี่ยนแปลงในความจุเวกเตอร์และต้นทุนของการแทรกเมื่อขนาดเติบโตขึ้นจาก 0 ถึง 18 ; นั่นคือโต๊ะ - dicates การเปลี่ยนแปลงในเวกเตอร์ในลำดับ 18 ครั้งเป็นเวกเตอร์ที่ว่างเปล่าในตอนแรก ตัวอย่างเช่น หากมีองค์ประกอบทั้งสี่ในเวกเตอร์ ( ขนาด = 4 ) แล้ว