سوالات المپیاد:دوره ی تابستان:دوره ی ۱۶:الگوریتم ها:سوال ۴
مرتب‌سازی درغامی
الگوریتم (Inserge-Sort(A که هدف‌ش مرتّب‌سازی آرایه‌ی $A$ است، بدین صورت است:
- $n$ $\leftarrow$ Length($A$);
- $k$ $\leftarrow$ Random($1$, $\lfloor\frac{n}{2}\rfloor$);
- Insertion-Sort($A[1..k]$);
- Inserge-Sort($A[k+1..n]$);
- Merge($A[1..k], A[k+1..n]$);
که منظور از $A[x..y]$، زیرآرایه‌ی شامل $A[x]$ تا $A[y]$ است و تابع ($y$,$x$)Random یک عدد تصادفی در بازه‌ی $[x,y]$ برمی‌گرداند.
رابطه‌ی بازگشتی زمان اجرای این الگوریتم را بر حسب $n$ نوشته و زمان اجرای متوسّط آن را صریحاً تحلیل کنید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
