The topic of the efficiency of radi

The topic of the efficiency of radix sort compared to other sorting algorithms is somewhat tricky and subject to quite a lot of misunderstandings. Whether radix sort is equally efficient, less efficient or more efficient than the best comparison-based algorithms depends on the details of the assumptions made. Radix sort efficiency is O(d·n) for n keys which have d or fewer digits. Sometimes d is presented as a constant, which would make radix sort better (for sufficiently large n) than the best comparison-based sorting algorithms, which are all O(n·log(n)) number of comparisons needed. However, in general d cannot be considered a constant. In particular, under the common (but sometimes implicit) assumption that all keys are distinct, then d must be at least of the order of log(n), which gives at best (with densely packed keys) a time complexity O(n·log(n)). That would seem to make radix sort at most equally efficient as the best comparison-based sorts (and worse if keys are much longer than log(n)).

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

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

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

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

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

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