۰
subtitle
ارسال: #۱
مرتب سازی آرایه
سلام
این سوال علوم کامپیوتر ۸۷ ،لطفا بگین چطور حل شده؟
با تشکر
برای مرتب سازی آرایه ای با ۲۰۰۰ عضو از الگوریتم randomized quick sort استفاده شده اگر call stackبرنامه در شروع الگوریتم خالی باشه و برای هر فراخوانی تابع تنها ۴ بایت آدرس برگشت در call stack قرار گیرد در طی این فراخوانی حواکثر طول اشغال شده call stack به طور متوسط چقدر خواهد بود؟؟
جواب : ۴۴ بایت
این سوال علوم کامپیوتر ۸۷ ،لطفا بگین چطور حل شده؟
با تشکر
برای مرتب سازی آرایه ای با ۲۰۰۰ عضو از الگوریتم randomized quick sort استفاده شده اگر call stackبرنامه در شروع الگوریتم خالی باشه و برای هر فراخوانی تابع تنها ۴ بایت آدرس برگشت در call stack قرار گیرد در طی این فراخوانی حواکثر طول اشغال شده call stack به طور متوسط چقدر خواهد بود؟؟
جواب : ۴۴ بایت
۰
ارسال: #۲
RE: مرتب سازی آرایه
(۲۲ دى ۱۳۹۱ ۱۲:۵۶ ق.ظ)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 ضرب کنید.
----------
برای از اطلاعات بیشتر به ویکی پدیا مراجعه بفرمایید:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
دو حالت دیگه هم داره :
یکی ( لگاریتگم n) به توان ۲
یکی nlogn در بدترین حالت
--
که بعد از یافتن جواب باید در bit یا byte ضرب کنید.
----------
برای از اطلاعات بیشتر به ویکی پدیا مراجعه بفرمایید:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close