As a data-oblivious algorithm, our

As a data-oblivious algorithm, our randomized Shellsort
method is a Monte Carlo algorithm (e.g., see [32,33]), in that
it always runs in the same amount of time but can sometimes
fail to sort. It can easily be converted into a data-dependent
Las Vegas algorithm, however, which always succeeds but
has a randomized running time, by testing if its output is
sorted and repeating the algorithm if it is not. Such a datadependent
version of randomized Shellsort would run in
O(n log n) time with very high probability; hence, it would
provide the first version of Shellsort that provably runs in
O(n log n) time with very high probability.

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

เป็นอัลกอริธึมข้อมูลขยี้ Shellsort ของเราแบบสุ่มวิธีคือ ขั้นตอนวิธีการมอนติคาร์โล (เช่น ดู [32,33]), ในที่มันควรทำงานในระยะเวลาแต่บางครั้งเดียวกันไม่สามารถเรียงลำดับ มันสามารถแปลงเป็นข้อมูลขึ้นอยู่กับขั้นตอนวิธีลาสเวกัส อย่างไรก็ตาม ซึ่งมักจะสำเร็จ แต่มีเวลาทำงานแบบสุ่ม โดยทดสอบว่าผลลัพธ์เรียงลำดับ และอัลกอริทึมในการทำซ้ำไม่ Datadependent การดังกล่าวรุ่น Shellsort สุ่มจะทำงานในเวลา O (n n บันทึก) กับความน่าเป็นสูงมาก ด้วยเหตุนี้ มันจะรุ่นแรกของ Shellsort ที่ provably ให้เวลา O (n n บันทึก) กับความเป็นไปได้สูงมาก

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

ในฐานะที่เป็นอัลกอริทึมข้อมูลลืม Shellsort เราสุ่ม
วิธีการเป็นขั้นตอนวิธี Monte Carlo (เช่นเห็น [32,33]) ในการที่
มันก็จะทำงานในระยะเวลาเดียวกัน แต่บางครั้งอาจ
ล้มเหลวในการจัดเรียง มันสามารถจะแปลงเป็นข้อมูลขึ้นอยู่กับ
อัลกอริทึมลาสเวกัอย่างไรซึ่งมักจะประสบความสำเร็จ แต่
มีเวลาในการทำงานแบบสุ่มโดยการทดสอบถ้าผลลัพธ์ของมันจะถูก
เรียงลำดับและขั้นตอนวิธีการทำซ้ำถ้ามันไม่ได้ เช่น datadependent
รุ่นสุ่ม Shellsort จะทำงานใน
O (n log n) เวลามีโอกาสสูงมาก ด้วยเหตุนี้มันจะ
ให้รุ่นแรกของสรรพสิ่ง Shellsort ที่ทำงานใน
O (n log n) เวลาที่มีความน่าจะเป็นสูงมาก

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

เป็นข้อมูลที่เรา shellsort ลบเลือนขั้นตอนวิธีวิธีคือวิธีมอนติคาร์โล ( เช่น ดู [ 32,33 ] ) , ในที่มันมักจะเกิดขึ้นในเวลาเท่ากัน แต่บางครั้งสามารถล้มเหลวในการจัดเรียง มันสามารถแปลงเป็นข้อมูลที่ขึ้นอยู่กับขั้นตอนวิธีลาสเวกัส , อย่างไรก็ตาม , ซึ่งมักจะสำเร็จ แต่มีคนวิ่งเวลาโดยการทดสอบ หากผลผลิตของตนคือเรียงตามขั้นตอนวิธีการและถ้ามันไม่ได้เป็น เช่น datadependentรุ่นที่ shellsort จะวิ่งในO ( n log n ) เวลาที่มีความน่าจะเป็นสูงมาก ดังนั้น จะให้รุ่นแรกของ shellsort ที่อาจทำงานในO ( n log n ) เวลาที่มีความน่าจะเป็นสูงมาก