เมนูนำทาง
การเรียงลำดับเพชันส์ การวิเคราะห์ขั้นตอนแรกของ patience sort การจำลองเกมการ์ดสามารถใช้เพื่อเปรียบเทียบ O (n log n) ในกรณีที่เลวร้ายที่สุดสำหรับอาร์เรย์ข้อมูล n-element: จะมีกอง n ส่วนใหญ่และโดยการก่อสร้างด้านบน ไพ่ของกองแบบฟอร์มลำดับที่เพิ่มขึ้นจากซ้ายไปขวาดังนั้นกองที่ต้องการสามารถพบได้โดยการค้นหาแบบไบนารี ระยะที่สองการรวมกองสามารถทำได้ในเวลา O (n log n) ด้วยการใช้การเข้าคิวลำดับความสำคัญ
เมื่อข้อมูลอินพุตมีข้อมูล "ทำงาน" ตามธรรมชาติเช่นโครงสร้างย่อยที่ไม่ลดลงประสิทธิภาพจะดีขึ้นอย่างเห็นได้ชัด ในความเป็นจริงเมื่ออาร์เรย์อินพุตถูกจัดเรียงเรียบร้อยแล้วค่าทั้งหมดจะเป็นแบบกองเดียวและทั้งสองเฟสจะทำงานในเวลา O (n) ความซับซ้อนของกรณีโดยเฉลี่ยยังคงเป็น O (n log n): ลำดับสุ่มของค่าใด ๆ จะให้จำนวน O (√n) ที่คาดหวังไว้, ซึ่งใช้เวลา O (n log √n) = O (n log n) เวลาในการผลิตและผสาน
การประเมินผลการปฏิบัติงานของ patience sort คือ Chandramouli และ Goldstein ผู้แสดงให้เห็นว่า naive version ช้ากว่า quicksort เป็นเวลาประมาณสิบถึงยี่สิบนาที quicksort บนปัญหามาตรฐานของพวกเขา พวกเขาให้เหตุผลว่าเป็นการวิจัยเชิงปริมาณเพียงเล็กน้อยของ patience sort และพัฒนาการเพิ่มประสิทธิภาพหลายอย่างซึ่งจะทำให้ประสิทธิภาพการทำงานของมันอยู่ในระดับที่สองของ quicksort
ถ้าค่าของการ์ดอยู่ในช่วง 1,....,n, มีการใช้งานที่มีประสิทธิภาพด้วย O (n log log n) เวลาทำงานที่เลวร้ายที่สุด (worst-case) สำหรับการใส่ไพ่ลงกองโดยใช้ต้นไม้ Van Emde Boas
Patience sorting มีความเกี่ยวข้องกับเกมไพ่ที่เรียกว่าเกม Floyd เกมนี้มีความคล้ายคลึงกับเกมที่ร่างไว้ก่อนหน้านี้:
1. บัตรแรกที่แจกให้เป็นกองใหม่ประกอบด้วยการ์ดใบเดียว
2. การ์ดใบใดก็ตามที่มีอยู่จะถูกวางลงบนกองที่มีอยู่ซึ่งการ์ดด้านบนมีค่าไม่เกินมูลค่าของบัตรใหม่หรือด้านขวาของไพ่ทั้งหมดที่มีอยู่แล้วจึงเป็นกองใหม่
3. เมื่อไม่มีไพ่เหลืออยู่อีกแล้วเกมจะสิ้นสุดลง
เป้าหมายของเกมคือการจบด้วยกองน้อยที่สุดเท่าที่จะเป็นไปได้ ความแตกต่างกับอัลกอริธึม Patience sorting คือไม่จำเป็นต้องวางการ์ดใบใหม่ไว้ที่กองซ้ายสุดซึ่งจะได้รับอนุญาต การเรียงลำดับความอดทนถือเป็นกลยุทธ์ greedy ในการเล่นเกมนี้
Aldous และ Diaconis แนะนำให้กำหนดกอง 9 หรือน้อยกว่าเป็นผลลัพธ์ที่ดีสำหรับ n = 52 ซึ่งเกิดขึ้นได้ด้วยความน่าจะเป็นประมาณ 5%
ขั้นแรกให้รันอัลกอริทึมการเรียงลำดับตามที่อธิบายไว้ด้านบน จำนวนกองเป็นความยาวของบันไดที่ยาวที่สุด เมื่อใดก็ตามที่มีการวางไพ่ขึ้นด้านบนของกองให้วางตัวชี้กลับไปที่ด้านบนของไพ่ในกองก่อนหน้านี้ (ที่โดยสมมติฐานมีค่าต่ำกว่าการ์ดใบใหม่มี) ในตอนท้ายให้ทำตามตัวชี้ด้านหลังจากด้านบนของไพ่ในกองสุดท้ายเพื่อกู้คืนความยาวที่ลดลงของความยาวที่ยาวที่สุด ย้อนกลับของมันคือคำตอบของอัลกอริธึมย่อยที่เพิ่มขึ้นที่ยาวที่สุด
S. Bespamyatnikh และ M. Segal ให้คำอธิบายเกี่ยวกับการใช้อัลกอริธึมที่มีประสิทธิภาพโดยไม่ก่อให้เกิดค่าใช้จ่ายเพิ่มเติมในการจัดเรียง (เนื่องจากการจัดเก็บข้อมูลการสร้างและการข้ามผ่านแบบย้อนหลังต้องใช้เวลาและพื้นที่เชิงเส้น) พวกเขายังแสดงวิธีการรายงานข้อมูลที่ยาวที่สุดทั้งหมดที่เพิ่มขึ้นจากโครงสร้างข้อมูลผลลัพธ์ที่เหมือนกัน
เมนูนำทาง
การเรียงลำดับเพชันส์ การวิเคราะห์ใกล้เคียง
การเรียนรู้ของเครื่อง การเร่งปฏิกิริยา การเรียนรู้เชิงลึก การเรืองแสงของบรรยากาศ การเร็นเดอร์ การเรียน การเรียงลำดับแบบฟอง การเรียกชื่อสารเคมีตามระบบไอยูแพ็ก การเรียกยานพาหนะคืนของโตโยต้า พ.ศ. 2552−2553 การเร่งโดยอาศัยแอนติบอดีแหล่งที่มา
WikiPedia: การเรียงลำดับเพชันส์ http://research.microsoft.com/pubs/209622/patsort-...