Processing math: 37%

سوالات المپیاد:دوره ی تابستان:دوره ی ۱۶:الگوریتم ها:سوال ۶

کپه‌ی بازگشتی

رویه‌ی Build-Heap را برای تبدیل آرایه‌ی ‎ $A[1..n]$ ‎ به یک هیپ در نظر بگیرید:

Build-Heap( $A$ ) ‎

‎for $i\leftarrow \lfloor Length(A)/2 \rfloor$ downto $‎1$ ‎
do ‎Bubble-Down(A‎, ‎i);‎

رویه‌ی فوق را به صورت رویه‌ی بازگشتی Recursive-Build-Heap( $A‎, ‎i$ )‎ به زبان ‎ $CLRS$ ‎ بازنویسی کنید، طوری که $‎A[i]‎$ ریشه‌ی‎«زیر-هیپ»ی است که قرار است ساخته شود. برای تبدیل کل آرایه به یک هیپ باید رویه را به‌صورت Recursive-Build-Heap( $A‎,‎1$ )‎ فرا بخوانیم.
زمان اجرای الگوریتم خود را در بدترین حالت، به‌صورت یک رابطه‌ی بازگشتی بنویسید.
رابطه‌ی بازگشتی به‌دست آمده را با استفاده از قضیه‌ی اصلی حل کنید.