ประสิทธิภาพการเรียงลำดับ Radix และ O(N log N)

ฉันได้เรียนรู้เกี่ยวกับการเรียงลำดับ Radix เมื่อเร็ว ๆ นี้ และหนึ่งในแหล่งข้อมูลที่ฉันใช้คือหน้า Wikipedia ในขณะนี้มีย่อหน้าต่อไปนี้เกี่ยวกับประสิทธิภาพของอัลกอริทึม:

หัวข้อประสิทธิภาพของการเรียงลำดับ Radix เมื่อเปรียบเทียบกับอัลกอริธึมการเรียงลำดับอื่นๆ นั้นค่อนข้างยุ่งยากและอาจมีความเข้าใจผิดค่อนข้างมาก การเรียงลำดับ Radix จะมีประสิทธิภาพเท่ากัน มีประสิทธิภาพน้อยกว่า หรือมีประสิทธิภาพมากกว่าอัลกอริธึมที่ใช้การเปรียบเทียบที่ดีที่สุดหรือไม่ ขึ้นอยู่กับรายละเอียดของสมมติฐานที่ทำขึ้น ความซับซ้อนในการเรียงลำดับ Radix คือ O(wn) สำหรับคีย์ n ซึ่งเป็นจำนวนเต็มขนาดคำ w บางครั้ง w จะถูกนำเสนอเป็นค่าคงที่ ซึ่งจะทำให้การเรียงลำดับ Radix ดีขึ้น (สำหรับ n ที่มีขนาดใหญ่เพียงพอ) มากกว่าอัลกอริธึมการเรียงลำดับตามการเปรียบเทียบที่ดีที่สุด ซึ่งทั้งหมดจะทำการเปรียบเทียบ O(n log n) เพื่อเรียงลำดับ n คีย์ อย่างไรก็ตาม โดยทั่วไป w ไม่สามารถถือเป็นค่าคงที่ได้: หากคีย์ n ทั้งหมดแตกต่างกัน อย่างน้อย w จะต้องมีบันทึก n เพื่อให้เครื่องที่เข้าถึงโดยสุ่มสามารถจัดเก็บไว้ในหน่วยความจำ ซึ่งให้ ความซับซ้อนของเวลาที่ดีที่สุด O(n log n) นั่นดูเหมือนจะทำให้การเรียงลำดับ Radix มีประสิทธิภาพเท่าเทียมกันมากที่สุดกับการเรียงลำดับตามการเปรียบเทียบที่ดีที่สุด (และแย่กว่านั้นถ้าคีย์ยาวกว่า log n มาก) .

ส่วนที่เป็นตัวหนากลายเป็นอุปสรรคที่ฉันไม่สามารถผ่านไปได้ ฉันเข้าใจว่าโดยทั่วไปการเรียงลำดับ Radix คือ O(wn) และจากแหล่งข้อมูลอื่น ๆ ได้เห็นว่า O(n) สามารถทำได้อย่างไร แต่ไม่เข้าใจว่าทำไม n คีย์ที่แตกต่างกันจึงต้องใช้เวลา O(n log n) ในการจัดเก็บในรูปแบบสุ่ม เข้าถึงเครื่อง ฉันค่อนข้างแน่ใจว่ามันขึ้นอยู่กับคณิตศาสตร์ง่ายๆ แต่น่าเสียดายที่ความเข้าใจที่มั่นคงยังคงอยู่นอกเหนือความเข้าใจของฉัน

ความพยายามที่ใกล้ที่สุดของฉันมีดังนี้:

เมื่อกำหนดฐาน 'B' และตัวเลขในฐานนั้น 'N' ตัวเลขสูงสุด 'N' สามารถมีได้คือ:

(ล็อกB ของ N) + 1

หากตัวเลขแต่ละตัวในรายการที่กำหนด L ไม่ซ้ำกัน เราจะได้มากถึง:

L *((logB ของ N) + 1) ความเป็นไปได้

ถึงจุดนั้นฉันไม่แน่ใจว่าจะก้าวหน้าไปอย่างไร

มีใครช่วยขยายส่วนด้านบนด้วยตัวหนาและแจกแจงว่าทำไม n คีย์ที่แตกต่างกันจึงต้องการบันทึกขั้นต่ำสำหรับพื้นที่เก็บข้อมูลที่เข้าถึงโดยสุ่ม


sorting big-o radix-sort
person Levenal    schedule 25.01.2018    source แหล่งที่มา

คำตอบ (1)


arrow_upward
0
arrow_downward

สมมติว่า MSB radix เรียงลำดับด้วยค่าคงที่ m bins:

  • สำหรับประเภทข้อมูลขนาดใหญ่ตามอำเภอใจซึ่งต้องรองรับค่าที่แตกต่างกันอย่างน้อย n จำนวนบิตที่ต้องการคือ N = ceiling(log2(n))
  • ดังนั้นจำนวนหน่วยความจำที่ต้องใช้ในการจัดเก็บแต่ละค่าจึงเป็น O(log n); สมมติว่าเข้าถึงหน่วยความจำตามลำดับ ความซับซ้อนของเวลาในการอ่าน / เขียนค่าคือ O(N) = O(log n) แม้ว่าจะสามารถใช้พอยน์เตอร์แทนได้
  • จำนวนหลักคือ O(N / m) = O(log n)
  • ที่สำคัญ แต่ละหลักที่อยู่ติดกันจะต้องต่างกันด้วยเลขยกกำลัง 2 กล่าวคือ m จะต้องเป็นเลขยกกำลัง 2 ด้วย ถือว่าสิ่งนี้มีขนาดเล็กพอสำหรับแพลตฟอร์ม HW เช่น ตัวเลข 4 บิต = 16 ถังขยะ

ระหว่างการเรียงลำดับ:

  • สำหรับแต่ละการส่งผ่าน Radix ซึ่งมี O(log n):

    1. Count each bucket: get the value of the current digit using bit operations - O(1) for all n values. Should note that each counter must also be N bits, although increments by 1 will be (amortized) O(1). If we had used non-power-of-2 digits, this would in general be O(log n log log n) ( source )

    2. ทำให้อาร์เรย์การนับที่เก็บข้อมูลสะสม: ต้องดำเนินการเพิ่ม m - 1 ซึ่งแต่ละรายการคือ O(N) = O(log n) (ไม่เหมือนกับกรณีพิเศษที่เพิ่มขึ้น)

    3. เขียนอาร์เรย์เอาต์พุต: วนซ้ำค่า n กำหนดถังขยะอีกครั้ง และเขียนตัวชี้ด้วยออฟเซ็ตที่ถูกต้อง

ดังนั้นความซับซ้อนทั้งหมดคือ O(log n) * [ n * O(1) + m * O(log n) + n * O(1) ] = O(n log n)

person meowgoesthedog    schedule 25.01.2018
comment
ขอบคุณสำหรับคำตอบ ส่วนประเด็นที่ 4 เป็นเพียงความเห็นทั่วไปหรือเปล่าครับ? เนื่องจากการเรียงลำดับ Radix ไม่ได้ทำการเปรียบเทียบใด ๆ เท่าที่ฉันรู้ - person Levenal; 26.01.2018
comment
@Levenal ขอโทษอย่างชัดเจน My_Brain.exe has encountered a problem and has to close - person meowgoesthedog; 26.01.2018
comment
ฉันขอแนะนำให้รีบูต =) การแก้ไขมีประโยชน์มากขอบคุณ การทำลายมันลงตามที่คุณทำจะทำให้ทำงานได้ง่ายขึ้น ฉันยังเข้าใจไม่หมด แต่ตอนนี้มีความมั่นใจมากขึ้นในการไปถึงจุดนั้น - person Levenal; 26.01.2018