محل شما: المپیاد کامپیوتر » سوال‌های المپیاد » آزمون‌‌های دوره‌ی تابستان » دوره‌ی ۱۶ » آزمون الگوریتم - تابستان ۸۵ » کپه‌ی بازگشتی

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

رویه‌ی 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$) فرا بخوانیم.
زمان اجرای الگوریتم خود را در بدترین حالت، به‌صورت یک رابطه‌ی بازگشتی بنویسید.
رابطه‌ی بازگشتی به‌دست آمده را با استفاده از قضیه‌ی اصلی حل کنید.