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 efficiencies for each operation. But this may result in an excessively large and unrealistic 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 array 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 additions, the array is nearly sorted. Thus, it should be quicker to put all elements in perfect 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 complexity 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 ที่มีผลต่อเวลาของการดำเนินงานถัดไปในลำดับ ต่าง ๆ แบบประเมินกรณีเลวร้ายที่สุดที่รันไทม์ของลำดับทั้งเป็นการ เพิ่มประสิทธิภาพกรณีเลวร้ายที่สุดสำหรับแต่ละการดำเนินการ แต่นี้อาจทำให้มีขนาดใหญ่มากเกินไป และไม่ผูกในเวลาจริง จะสมจริงมากขึ้น สามารถใช้วิเคราะห์ซึ่งตัดจำหน่ายหาความซับซ้อนที่เฉลี่ยของลำดับกรณีเลวร้ายที่สุดของการดำเนินงาน โดยการวิเคราะห์ลำดับของการดำเนินงานมากกว่าที่แยกการดำเนินงาน วิเคราะห์ซึ่งตัดจำหน่ายจะเป็นอิสระเสรีบัญชีระหว่างการดำเนินการและผลลัพธ์ ตัวอย่างเช่น ถ้าเป็นแถวเรียงลำดับเท่านั้น และการเพิ่มองค์ประกอบใหม่น้อยมาก แล้วการเรียงลำดับแถวลำดับนี้ควรจะเร็วกว่าการเรียงลำดับในครั้งแรกเนื่องจาก หลังจากที่เพิ่มใหม่ อาร์เรย์เกือบเรียงลำดับ ดังนั้น มันควรจะเร็วกว่าการใส่องค์ประกอบทั้งหมดในลำดับโกในอาร์เรย์เป็นโล้เป็นพายอย่างสมบูรณ์ โดยไม่ต้องการความสัมพันธ์นี้เข้าบัญชี เวลาของการดำเนินการเรียงลำดับที่สองถือได้ว่าสองครั้งเลวร้ายที่สุดกรณีประสิทธิภาพ วิเคราะห์ซึ่งตัดจำหน่าย คง ตัดสินใจว่า เรียงลำดับสองแทบไม่ใช้ในกรณีสถานการณ์เลวร้ายที่สุดที่รวมความซับซ้อนของการดำเนินการเรียงลำดับที่สอง น้อยกว่าคู่ที่เลวร้ายที่สุดกรณีซับซ้อน ดังนั้น ลำดับกรณีเลวร้ายที่สุดของการเรียง ลำดับ การแทรกกี่ และการเรียงลำดับค่าเฉลี่ยอีกอยู่ล่างตามวิเคราะห์ซึ่งตัดจำหน่ายกว่าตามการวิเคราะห์กรณีเลวร้ายที่สุด ซึ่งไม่คำนึงถึงข้อเท็จจริงว่า การเรียงลำดับที่สองจะใช้กับอาร์เรย์ที่ดำเนินการบนแล้ว โดยการเรียงลำดับก่อนหน้า

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

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

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

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