In many situations, data structures

In many situations, data structures are subject to a sequence of operations rather than one operation. In this sequence, one operation possibly performs certain modifica- tions that have an impact on the run time of the next operation in the sequence. One way of assessing the worst case run time of the entire sequence is to add worst case ef- ficiencies for each operation. But this may result in an excessively large and unrealis- tic bound on the actual run time. To be more realistic, amortized analysis can be used to find the average complexity of a worst case sequence of operations. By analyzing sequences of operations rather than isolated operations, amortized analysis takes into account interdependence between operations and their results. For example, if an ar- ray is sorted and only a very few new elements are added, then re-sorting this array should be much faster than sorting it for the first time because, after the new addi- tions, the array is nearly sorted. Thus, it should be quicker to put all elements in per- fect order than in a completely disorganized array. Without taking this correlation into account, the run time of the two sorting operations can be considered twice the worst case efficiency. Amortized analysis, on the other hand, decides that the second sorting is hardly applied in the worst case situation so that the combined complex- ity of the two sorting operations is much less than double the worst case complexity. Consequently, the average for the worst case sequence of sorting, a few insertions, and sorting again is lower according to amortized analysis than according to worst case analysis, which disregards the fact that the second sorting is applied to an array operated on already by a previous sorting.

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

ในสถานการณ์ต่าง ๆ โครงสร้างข้อมูลจะขึ้นอยู่กับลำดับของการดำเนินงานมากกว่ากัน ในลำดับนี้ กันอาจทำบาง modifica-tions ที่มีผลต่อเวลาของการดำเนินงานถัดไปในลำดับ ต่าง ๆ แบบประเมินกรณีเลวร้ายที่สุดที่รันไทม์ของลำดับทั้งจะเพิ่ม ficiencies กรณี ef เลวร้ายที่สุดสำหรับแต่ละการดำเนินการ แต่นี้อาจทำให้มีขนาดใหญ่มากเกินไป และรับผลิตกระป๋อง unrealis ผูกในเวลาจริง จะสมจริงมากขึ้น สามารถใช้วิเคราะห์ซึ่งตัดจำหน่ายหาความซับซ้อนที่เฉลี่ยของลำดับกรณีเลวร้ายที่สุดของการดำเนินงาน โดยการวิเคราะห์ลำดับของการดำเนินงานมากกว่าที่แยกการดำเนินงาน วิเคราะห์ซึ่งตัดจำหน่ายจะเป็นอิสระเสรีบัญชีระหว่างการดำเนินการและผลลัพธ์ ตัวอย่างเช่น ถ้าเป็น ar-เรย์เท่านั้น และเรียงลำดับการเพิ่มองค์ประกอบใหม่น้อยมาก แล้วการเรียงลำดับแถวลำดับนี้ควรจะเร็วกว่าการเรียงลำดับในครั้งแรกเนื่องจาก หลังจากใหม่ addi-tions อาร์เรย์เกือบเรียงลำดับ ดังนั้น มันควรจะเร็วกว่าการใส่องค์ประกอบทั้งหมดในต่อ fect ลำดับในอาร์เรย์เป็นโล้เป็นพายอย่างสมบูรณ์ โดยไม่ต้องการความสัมพันธ์นี้เข้าบัญชี เวลาของการดำเนินการเรียงลำดับที่สองถือได้ว่าสองครั้งเลวร้ายที่สุดกรณีประสิทธิภาพ วิเคราะห์ซึ่งตัดจำหน่าย คง ตัดสินใจว่า เรียงลำดับสองแทบไม่ใช้ในกรณีสถานการณ์เลวร้ายที่สุดที่ซับซ้อน-ity รวมของการดำเนินการเรียงลำดับที่สอง น้อยกว่าคู่ที่เลวร้ายที่สุดกรณีซับซ้อน ดังนั้น ลำดับกรณีเลวร้ายที่สุดของการเรียง ลำดับ การแทรกกี่ และการเรียงลำดับค่าเฉลี่ยอีกอยู่ล่างตามวิเคราะห์ซึ่งตัดจำหน่ายกว่าตามการวิเคราะห์กรณีเลวร้ายที่สุด ซึ่งไม่คำนึงถึงข้อเท็จจริงว่า การเรียงลำดับที่สองจะใช้กับอาร์เรย์ที่ดำเนินการบนแล้ว โดยการเรียงลำดับก่อนหน้า

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

ในหลาย ๆ สถานการณ์โครงสร้างข้อมูลอาจมีการลำดับของการดำเนินงานมากกว่าหนึ่งการดำเนินงาน ในลำดับนี้การดำเนินการอย่างใดอย่างหนึ่งอาจจะดำเนินการทั้งนี้ modifica- บางอย่างที่มีผลกระทบต่อเวลาทำงานของการดำเนินการต่อไปในลำดับที่ วิธีการหนึ่งของการประเมินกรณีที่เวลาทำงานที่เลวร้ายที่สุดของลำดับทั้งหมดคือการเพิ่ม ficiencies กรณีที่เลวร้ายประสิทธิผลในการดำเนินงานแต่ละ แต่วิธีนี้อาจส่งผลในการกระตุกมากเกินไปขนาดใหญ่และ unrealis- ผูกพันในเวลาระยะที่เกิดขึ้นจริง การจะมีความสมจริงมากขึ้นการวิเคราะห์ตัดจำหน่ายสามารถใช้ในการหาค่าเฉลี่ยของความซับซ้อนลำดับกรณีที่เลวร้ายของการดำเนินงาน โดยการวิเคราะห์ลำดับของการดำเนินงานมากกว่าการดำเนินงานแยกวิเคราะห์ตัดจำหน่ายจะเข้าสู่การพึ่งพากันระหว่างบัญชีการดำเนินงานและผลของพวกเขา ตัวอย่างเช่นถ้าเรย์ ar- เรียงและมีเพียงองค์ประกอบใหม่น้อยมากที่จะมีการเพิ่มแล้วเรียงลำดับใหม่อาร์เรย์นี้ควรจะเร็วกว่าการเรียงลำดับเป็นครั้งแรกเพราะหลังจากที่ข้อแก้ที่ดีนอกจากใหม่อาร์เรย์เกือบ เรียง ดังนั้นจึงควรจะรวดเร็วในการวางองค์ประกอบทั้งหมดในการสั่งซื้อส่ละกว่าในอาร์เรย์ที่ไม่เป็นระเบียบอย่างสมบูรณ์ โดยไม่คำนึงถึงความสัมพันธ์นี้ในบัญชีที่เวลาทำงานของทั้งสองดำเนินการเรียงลำดับได้รับการพิจารณาเป็นครั้งที่สองอย่างมีประสิทธิภาพกรณีที่เลวร้าย การวิเคราะห์การตัดจำหน่ายในมืออื่น ๆ ตัดสินใจว่าการเรียงลำดับที่สองแทบจะไม่ถูกนำไปใช้ในสถานการณ์ที่เลวร้ายที่สุดกรณีเพื่อให้ ity complex- รวมของทั้งสองดำเนินการเรียงลำดับมีมากน้อยกว่าสองเท่าของความซับซ้อนกรณีที่เลวร้าย ดังนั้นเฉลี่ยสำหรับลำดับกรณีที่เลวร้ายที่สุดของการเรียงลำดับการแทรกไม่กี่และการเรียงลำดับอีกครั้งลดลงตามการวิเคราะห์ตัดจำหน่ายกว่าตามการวิเคราะห์กรณีที่เลวร้ายซึ่งสภาพแวดล้อมความเป็นจริงว่าการเรียงลำดับที่สองคือนำไปใช้กับอาร์เรย์ดำเนินการอยู่แล้วด้วย การเรียงลำดับก่อนหน้า

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

ในหลาย ๆสถานการณ์โครงสร้างข้อมูลและลำดับของการดำเนินการมากกว่าหนึ่งงาน ในลำดับนี้ การดำเนินการหนึ่งอาจดำเนินการบางอย่าง modifica - ยินดีด้วยที่ได้รับผลกระทบในเวลาเรียกใช้งานถัดไปในลำดับ วิธีการหนึ่งของการประเมินกรณีเลวร้ายที่สุด รันไทม์ของลำดับทั้งหมดคือการเพิ่มกรณีที่เลวร้ายที่สุด EF - ficiencies สำหรับแต่ละงานแต่นี้อาจส่งผลใน unrealis - มากเกินไปขนาดใหญ่และ TIC จำกัดในเวลาวิ่งจริง ต้องมีเหตุผลมากขึ้น ของขวัญที่สามารถใช้เพื่อค้นหาการวิเคราะห์ความซับซ้อนเฉลี่ยกรณีเลวร้ายที่สุดลำดับของการดำเนินการ โดยการวิเคราะห์ลำดับของการดำเนินการมากกว่าที่จะแยกการหักกลบลบล้างการวิเคราะห์คำนึงถึงการพึ่งพาอาศัยกันระหว่างการดำเนินการและผลลัพธ์ ตัวอย่างเช่นถ้าอาร์เรย์จะถูกจัดเรียงและเพียงไม่กี่มากองค์ประกอบใหม่จะถูกเพิ่ม แล้วเรียงลำดับอาร์เรย์น่าจะเร็วกว่าการจัดเรียงเป็นครั้งแรก เพราะหลังใหม่ addi - ยินดีด้วย อาร์เรย์เกือบเรียง . ดังนั้น มันควรจะเร็วใส่องค์ประกอบทั้งหมดในต่อ fect สั่งมากกว่าอย่างไม่เป็นระเบียบ เรย์ โดยไม่มีความสัมพันธ์นี้ลงในบัญชีวิ่งเวลาของทั้งสองแยกการดำเนินการสามารถพิจารณา 2 กรณีเลวร้ายที่สุดประสิทธิภาพ หักกลบลบล้างข้อมูลบนมืออื่น ๆที่เห็นว่าสองแยกจะใช้ในสถานการณ์ที่เลวร้ายที่สุดกรณีดังนั้น ity ซับซ้อนรวม - สอง การเรียงลำดับ การจะน้อยกว่าคู่กรณีที่เลวร้ายที่สุดของความซับซ้อน โดยเฉลี่ยสำหรับกรณีเลวร้ายที่สุด ลำดับของการเรียงลำดับไม่กี่ครั้ง และจัดเรียงใหม่จะลดลงตามการวิเคราะห์มากกว่าของขวัญตามการวิเคราะห์กรณีเลวร้ายที่สุด ซึ่งไม่สนใจข้อเท็จจริงที่ 2 การใช้ array ผ่าตัดเรียบร้อยแล้ว โดยก่อนหน้านี้มีการเรียงลำดับ