کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430987 | 688239 | 2007 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Asymptotic distributions for Random Median Quicksort
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The first complete running time analysis of a stochastic divide and conquer algorithm was given for Quicksort, a sorting algorithm invented 1961 by Hoare. We analyse here the variant Random Median Quicksort. The analysis includes the expectation, the asymptotic distribution, the moments and exponential moments. The asymptotic distribution is characterized by a stochastic fixed point equation. The basic technic will be generating functions and the contraction method.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 5, Issue 3, September 2007, Pages 592–608
Journal: Journal of Discrete Algorithms - Volume 5, Issue 3, September 2007, Pages 592–608
نویسندگان
H.M. Okasha, U. Rösler,