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