کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430457 | 687984 | 2009 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Efficient algorithms for the inverse sorting problem with bound constraints under the l∞-norm and the Hamming distance
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper, we study the inverse sorting problem with bound constraints under the l∞-norm and the Hamming distance. For the problem under the l∞-norm, an O(nlogn)-time algorithm is presented. For the problem under the Hamming distance, we first show that it has an Ω(nlogn)-time lower bound in the comparison model; and then, we present an O(nlogn)-time algorithm. Both of the presented algorithms improve the previous upper bounds from O(n2).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 75, Issue 8, December 2009, Pages 451-464
Journal: Journal of Computer and System Sciences - Volume 75, Issue 8, December 2009, Pages 451-464