دانلود مقاله ترجمه شده به سوی مرتب‌سازی سطلی بهینه

چکیده

ما یک الگوریتم موازی قطعی ساده که روی CRCW PRAM اجرا می‌شود و n عدد صحیح را در زمان چندجمله‌ای نسبت به n با مرتبه‌ی O(log n)  و با استفاده از O(n log log n/log n)پردازنده مرتب  می‌کند، ارائه می‌کنیم. این الگوریتم نسبت به الگوریتم‌های قطعی قبلی به بهینه نزدیک‌تر است و مسئله‌ی محدود مرتب‌سازی بیان شده را در زمان poly log حل می‌کند.

1-مقدمه

واضح است که n شیء از یک مجموعه‌ی مرتب کامل می‌تواند با n پردازنده در زمان O(log n) پردازنده، حتی با یک مدل بسیار ضعیف محاسبات موازی مانند شبکه پردازنده‌ی درجه محدود(فرض کنید مقایسه‌های باینری در یک واحد زمانی انجام می‌شوند) انجام شود. بهینه بودن نتیجه به این معناست که حاصل ضرب تعداد پردازنده‌ها در زمان لازم O(n log n) است، تا با یک کران زمانی کمتر Ω(n log n) برای هر الگوریتم ترتیبی عمل کننده بر اساس درخت تصمیم مقایسه شود. بنابراین هیچ الگوریتم مرتب‌سازی موازی کلی که در زمان O(log n) کار کند نمی‌تواند با o(n) پردازنده به این زمان دست یابد...