ความซับซ้อนของการเรียงลำดับการแทรกไบนารีสำหรับการแลกเปลี่ยนและการเปรียบเทียบในกรณีที่ดีที่สุด
อะไรคือความซับซ้อนของการเรียงลำดับการแทรกไบนารี? และมีการแลกเปลี่ยนและเปรียบเทียบจำนวนเท่าใด?
อาจเป็นการO(n(LG n))เปรียบเทียบ แต่ฉันไม่แน่ใจ สำหรับกรณีที่เลวร้ายที่สุดมันคือการN^2แลกเปลี่ยน สิ่งที่ดีที่สุด?
คำตอบ
คุณสามารถเขียนเรียงลำดับการแทรกไบนารีได้อย่างง่ายดายโดยใช้ประโยชน์จากฟังก์ชันในตัวเช่นbisect_leftและlist.pop(..)และlist.insert(..):
def bininssort(L):
n = len(L)
i,j=0,0
for i in range(1,n):
j=i-1
x=L.pop(i)
i1=bisect_left(L,x,0,j+1)
L.insert(i1,x)
return L
เกี่ยวกับกรณีที่แย่ที่สุดตั้งแต่ที่i-thทวนของวงที่เราดำเนินการค้นหาไบนารีภายในย่อยอาร์เรย์A[0..i]กับ0<=i<nที่ควรจะใช้เวลาlog(i)การดำเนินงานดังนั้นตอนนี้เรารู้ว่าเราต้องใส่องค์ประกอบที่ตำแหน่งที่ตั้งi1และเราใส่มัน แต่ การแทรกหมายความว่าเราต้องดันองค์ประกอบทั้งหมดที่ตามมาทางขวาหนึ่งตำแหน่งและนั่นคืออย่างน้อยn-iการดำเนินการ (อาจเป็นได้มากกว่าn-iการดำเนินการขึ้นอยู่กับตำแหน่งการแทรก) ถ้าเราสรุปสองอย่างนี้เราจะได้\sum_{i=1}^n log(i) + (n-i) = log(n!) + (n*(n+1))/2 ~ n*log(n) + (n*(n+1))/2
(ในข้างต้นประมาณของสเตอร์ลิงของlog(n!)จะถูกใช้)
ตอนนี้หน้าวิกิพูดว่า
ตามกฎทั่วไปเราสามารถสันนิษฐานได้ว่าคำที่มีลำดับสูงสุดในฟังก์ชันใดก็ตามที่มีอิทธิพลเหนืออัตราการเติบโตดังนั้นจึงกำหนดลำดับเวลาทำงาน
ดังนั้นฉันคิดว่าข้อสรุปน่าจะเป็นในกรณีที่เลวร้ายที่สุดการเรียงลำดับการแทรกไบนารีมีO(n^2)ความซับซ้อน
ดูสิ่งนี้ด้วย:
- การเรียงลำดับการแทรกโดยใช้การค้นหาแบบไบนารี
- การเรียงลำดับการแทรกด้วยการค้นหาแบบไบนารี
- การวิเคราะห์การเรียงลำดับการแทรกไบนารี
- การเรียงลำดับและความซับซ้อนของการแทรกไบนารี
จากนั้นฉันพยายามตรวจสอบว่ามันทำงานอย่างไรในรายการย้อนกลับ ( n,n-1,n-2,..,1) และรายการสลับ ( 0,n-1,1,n-2,2,n-3,...) และฉันติดตั้งมัน (โดยใช้โมดูลการจับคู่ ) กับอัตราการเติบโตที่แตกต่างกันส่วนนี้เป็นเพียงการประมาณเท่านั้น ลำดับที่ย้อนกลับได้รับการปรับให้พอดีกับเวลาพหุนามและลำดับการสลับจะพอดีกับเวลาควาซิลิเนียร์
ที่ดีที่สุดในกรณีที่มีการอธิบายที่นี่ ถ้ารายการจะถูกจัดเรียงอยู่แล้วแม้ว่าเราไม่ได้ทำสัญญาแลกเปลี่ยนใด ๆ O(n*log(n))ทั้งหมดการค้นหาไบนารีจะยังคงมีการดำเนินการที่จะนำไปสู่
รหัสที่ใช้ที่นี่มีอยู่ในที่เก็บนี้