Consider the operation of adding a

Consider the operation of adding a new element to the vector implemented as a flexible array. The best case is when the size of the vector is less than its capacity because adding a new element amounts to putting it in the first available cell. The cost of adding a new element is thus O(1). The worst case is when size equals capacity, in which case there is no room for new elements. In this case, new space must be allocated, the existng elements are copied to the new space, and only then can the new element be added to the vector. The cost of adding a new element is O(size(vector)). It is clear that the latter situation is less frequent than the former, but this depends on another parameter, capacity increment, which refers to how much the vector is increased when overflow occurs. In the extreme case, it can be incremented by just one cell, so in the sequence of m consecutive insertions, each insertion causes overflow and requires O(size(vector)) time to finish. Clearly, this situation should be delayed. One solution is to allocate, say, 1 million cells for the vector, which in most cases does not cause an overflow, but the amount of space is excessively large and only a small percentage of space allocated for the vector may be expected to be in actual use. Another solution to the problem is to double the space allocated for the vector if overflow occurs. In this case, the pessimistic O(size(vector)) performance of the insertion operation may be expected to occur only infrequently. By using this estimate, it may be claimed that, in the best case, the cost of inserting m items is O(m), but it is impossible to claim that, in the worst case, it is O(m # size(vector)). Therefore, to see better what impact this performance has on the sequence of operations, the amortized analysis should be used.

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

พิจารณาการเพิ่มองค์ประกอบใหม่ให้เวกเตอร์ใช้เป็นอาร์เรย์ที่มีความยืดหยุ่น กรณีดีที่สุดคือเมื่อขนาดของเวกเตอร์มีน้อยกว่ากำลังของมันเนื่องจากเพิ่มจำนวนองค์ประกอบตัวใหม่ในเซลล์แรกที่ว่าง ต้นทุนการเพิ่มองค์ประกอบใหม่จึง O(1) กรณีเลวร้ายที่สุดคือขนาดเท่ากับกำลังการผลิต ซึ่งมีกรณีมีห้องพักสำหรับองค์ประกอบใหม่ ในกรณีนี้ ต้องจัดสรรพื้นที่ใหม่ องค์ประกอบ existng จะถูกคัดลอกไปยังช่องใหม่ และหลังจากนั้น องค์ประกอบใหม่คุณสามารถเพิ่มเวกเตอร์ ต้นทุนการเพิ่มองค์ประกอบใหม่คือ O(size(vector)) เป็นที่ชัดเจนว่า สถานการณ์หลังเป็นบ่อยน้อยกว่าอดีต แต่ขึ้นอยู่กับพารามิเตอร์อื่น เพิ่มกำลัง ซึ่งหมายถึงเวกเตอร์จะเพิ่มขึ้นเท่าใดเมื่อเกิดมากเกินไป ในกรณีมาก มันสามารถเพิ่มเพียงหนึ่งเซลล์ ลำดับของ m ติดต่อกันแทรก แทรกแต่ละทำให้ล้น และต้อง O(size(vector)) เวลาเสร็จสิ้น ชัดเจน สถานการณ์นี้ควรจะล่าช้า วิธีการแก้ไขปัญหาคือการ ปันส่วน กล่าวว่า ล้านเซลล์สำหรับเวกเตอร์ ซึ่งเป็นกรณีทำให้เกิดโอเวอร์โฟลว์ แต่พื้นที่มีขนาดใหญ่มากเกินไป และเพียงเล็กน้อยของพื้นที่ที่จัดสรรสำหรับเวกเตอร์อาจจะคาดว่าจะใช้จริง แก้ไขปัญหาอื่นจะคู่พื้นที่จัดสรรสำหรับเวกเตอร์ถ้ามากเกินไปเกิดขึ้น ในกรณีนี้ ในเชิงลบ O(size(vector)) ประสิทธิภาพการทำงานของการแทรกอาจจะคาดว่าจะเกิดขึ้นนาน ๆ ครั้งเท่านั้น โดยใช้การประเมินนี้ อาจจะอ้างว่า ในกรณีดีที่สุด ต้นทุนของการแทรกรายการ m O(m) แต่เป็นไปอ้างว่า ในกรณีเลวร้ายที่สุด เป็น O (m # size(vector)) ดังนั้น เมื่อต้องการดูดีอะไรผลกระทบที่มีประสิทธิภาพนี้ในลำดับของการดำเนินงาน การวิเคราะห์ซึ่งตัดจำหน่ายควรใช้

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

พิจารณาการดำเนินงานของการเพิ่มองค์ประกอบใหม่ที่จะเวกเตอร์นำมาใช้เป็นอาร์เรย์ที่มีความยืดหยุ่น กรณีที่ดีที่สุดคือเมื่อขนาดของเวกเตอร์ที่มีน้อยกว่าความจุเนื่องจากการเพิ่มองค์ประกอบใหม่จำนวนเงินที่วางไว้ในเซลล์ที่มีอยู่ก่อน ค่าใช้จ่ายของการเพิ่มองค์ประกอบใหม่จึงเป็นโอนี้ (1) ในกรณีที่เลวร้ายที่สุดคือเมื่อขนาดเท่ากับกำลังการผลิตซึ่งในกรณีที่มีห้องพักสำหรับองค์ประกอบใหม่ไม่มี ในกรณีนี้พื้นที่ใหม่จะต้องได้รับการจัดสรรองค์ประกอบ existng ถูกคัดลอกไปพื้นที่ใหม่และเพียงแล้วองค์ประกอบใหม่สามารถเพิ่มเวกเตอร์ ค่าใช้จ่ายของการเพิ่มองค์ประกอบใหม่เป็น O (ขนาด (เวกเตอร์)) เป็นที่ชัดเจนว่าสถานการณ์หลังเป็นบ่อยน้อยกว่าเดิม แต่ตอนนี้ขึ้นอยู่กับพารามิเตอร์อื่นเพิ่มกำลังการผลิตซึ่งหมายถึงวิธีการมากเวกเตอร์จะเพิ่มขึ้นเมื่อล้นเกิดขึ้น ในกรณีที่รุนแรงก​​็สามารถเพิ่มขึ้นโดยเพียงแค่หนึ่งเซลล์ดังนั้นในลำดับของการแทรกติดต่อกันเป็นเมตรแต่ละแทรกทำให้เกิดน้ำล้นและต้องใช้ O (ขนาด (เวกเตอร์)) เวลาที่จะเสร็จสิ้น เห็นได้ชัดว่าสถานการณ์เช่นนี้ควรล่าช้า ทางออกหนึ่งคือการจัดสรรการพูด, 1 ล้านเซลล์เวกเตอร์ซึ่งในกรณีส่วนใหญ่ไม่ก่อให้เกิดน้ำล้น แต่จำนวนของพื้นที่ที่มีมากเกินไปขนาดใหญ่และมีเพียงไม่กี่เปอร์เซ็นต์ของพื้นที่ที่จัดสรรไว้เพื่อเวกเตอร์อาจจะคาดหวังที่จะอยู่ใน การใช้งานจริง วิธีการแก้ปัญหาที่เกิดขึ้นก็คือจะเป็นสองเท่าการจัดสรรพื้นที่สำหรับเวกเตอร์ถ้าล้นเกิดขึ้น ในกรณีนี้ในแง่ร้าย O (ขนาด (เวกเตอร์)) ผลการดำเนินงานของการดำเนินการแทรกอาจจะคาดว่าจะเกิดขึ้นเฉพาะบ่อย โดยใช้ประมาณนี้ก็อาจจะอ้างว่าในกรณีที่ดีที่สุด, ค่าใช้จ่ายของการใส่รายการเมตรเป็น O (m) แต่มันเป็นไปไม่ได้ที่จะเรียกร้องว่าในกรณีที่เลวร้ายที่สุดก็เป็น O (m ขนาด # (เวกเตอร์ )) ดังนั้นเพื่อที่จะเห็นสิ่งที่ดีกว่าผลกระทบต่อประสิทธิภาพในการนี​​้จะมีลำดับของการดำเนินการวิเคราะห์ตัดจำหน่ายควรจะใช้

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

พิจารณาการเพิ่มองค์ประกอบใหม่ในเวกเตอร์ที่ใช้เป็นแบบยืดหยุ่น กรณีที่ดีที่สุดคือเมื่อขนาดของเวกเตอร์น้อยกว่าความจุของมัน เพราะการเพิ่มจำนวนองค์ประกอบใหม่เพื่อใส่ในเซลล์ที่มีอยู่ก่อน ค่าใช้จ่ายของการเพิ่มองค์ประกอบใหม่จึงเป็น O ( 1 ) กรณีเลวร้ายที่สุดคือเมื่อขนาดเท่ากับความจุ ซึ่งในกรณีที่ไม่มีห้องสำหรับองค์ประกอบใหม่ ในกรณีนี้พื้นที่ใหม่จะต้องได้รับการจัดสรร , existng องค์ประกอบจะถูกคัดลอกไปยังพื้นที่ใหม่ และเพียงแล้วสามารถองค์ประกอบใหม่ที่ถูกเพิ่มไปยังเวกเตอร์ ค่าใช้จ่ายของการเพิ่มองค์ประกอบใหม่คือ O ( ขนาด ( เวกเตอร์ ) มันเป็นที่ชัดเจนว่าสถานการณ์หลังบ่อยน้อยลงกว่าเดิม แต่นี้ขึ้นอยู่กับค่าความจุเพิ่มอีก ซึ่งหมายถึงเท่าใดเวกเตอร์เพิ่มขึ้นเมื่อล้นเกิดขึ้นในกรณีที่รุนแรง ได้สั่งแค่เซลล์เพียงเซลล์เดียว ดังนั้นในลำดับของ M ครั้งติดต่อกัน แต่ละแทรกทำให้ล้นและต้องใช้ O ( ขนาด ( เวกเตอร์ ) เวลาที่จะเสร็จสิ้น เห็นได้ชัดว่าสถานการณ์นี้ควรจะต้องล่าช้า การจัดสรร , พูด , 1 ล้านเซลล์สำหรับเวกเตอร์ซึ่งในกรณีส่วนใหญ่ไม่ได้เพราะน้ำท่วมแต่ปริมาณของพื้นที่มากเกินไปขนาดใหญ่และเพียงร้อยละเล็ก ๆของพื้นที่ที่กำหนดสำหรับเวกเตอร์คาดว่าอาจจะถูกใช้งานจริง อีกแนวทางแก้ปัญหาเป็นสองเท่าจัดสรรพื้นที่สำหรับเวกเตอร์ถ้าท่วมเกิดขึ้น ในกรณีนี้ การมองโลกในแง่ร้าย แต่ขนาด ( เวกเตอร์ ) ประสิทธิภาพของการดำเนินงานคาดว่าอาจจะเกิดขึ้นเฉพาะแต่ไม่บ่อย โดยการใช้ประมาณนี้มันอาจจะอ้างว่า ในกรณีที่ดีที่สุด ต้นทุนของการแทรก m รายการคือ O ( M ) , แต่มันเป็นไปไม่ได้ที่จะเรียกร้องว่า ในกรณีเลวร้ายที่สุด มันคือ O ( ขนาด# M ( เวกเตอร์ ) ดังนั้น มาดูดีกว่าว่าผลกระทบต่อประสิทธิภาพนี้มีลำดับของการดำเนินงาน , ของขวัญการวิเคราะห์ควรใช้