سلام
این سوال علوم کامپیوتر ۸۷ ،لطفا بگین چطور حل شده؟
با تشکر
برای مرتب سازی آرایه ای با ۲۰۰۰ عضو از الگوریتم randomized quick sort استفاده شده اگر call stackبرنامه در شروع الگوریتم خالی باشه و برای هر فراخوانی تابع تنها ۴ بایت آدرس برگشت در call stack قرار گیرد در طی این فراخوانی حواکثر طول اشغال شده call stack به طور متوسط چقدر خواهد بود؟؟
جواب : ۴۴ بایت
(۲۲ دى ۱۳۹۱ ۱۲:۵۶ ق.ظ)jafarir نوشته شده توسط: سلام
این سوال علوم کامپیوتر ۸۷ ،لطفا بگین چطور حل شده؟
با تشکر
برای مرتب سازی آرایه ای با ۲۰۰۰ عضو از الگوریتم randomized quick sort استفاده شده اگر call stackبرنامه در شروع الگوریتم خالی باشه و برای هر فراخوانی تابع تنها ۴ بایت آدرس برگشت در call stack قرار گیرد در طی این فراخوانی حواکثر طول اشغال شده call stack به طور متوسط چقدر خواهد بود؟؟
جواب : ۴۴ بایت
به نظر من اینجوریه که چون در randomize quicksort عنصر pivot تقریبا وسط می افته پس تقریبا آرایه نصف میشه بعد برای هرکدوم آرایه های چپ و راست تابع فراخوانی میشه . و با هر بار فراخوانی ۴ بایت آدرس برگشت در پشته ذخیره میشه.
پس بطور متوسط [tex]\left \lceil log(2000) \right \rceil * 4 Byte = 44 Byte[/tex]
--------------------------
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
البته این حالت که کران بالای lgn میشه برای بهترین حالت یا حالت استفاده از پشته یا stack هست.
دو حالت دیگه هم داره :
یکی ( لگاریتگم n) به توان ۲
یکی nlogn در بدترین حالت
--
که بعد از یافتن جواب باید در bit یا byte ضرب کنید.
----------
برای از اطلاعات بیشتر به ویکی پدیا مراجعه بفرمایید:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.