زمان کنونی: ۲۱ آبان ۱۴۰۳, ۱۲:۳۳ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

حداکثر فضای پشته مورد نیاز برای اجرای الگوریتم QuickSort ؟

ارسال:
  

sos006 پرسیده:

حداکثر فضای پشته مورد نیاز برای اجرای الگوریتم QuickSort ؟

سلام.
در الگوریتم QuickSort حداکثر فضای پشته مورد نیاز برای اجرای این الگوریتم چه میزان است؟
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

parsaNA پاسخ داده:

RE: حداکثر فضای پشته مورد نیاز برای اجرای الگوریتم QuickSort ؟

با سلام.
حداکثر فضا اگر هر بار داده‌ها به طور مساوی تقسیم بشوند حداکثر عمق درخت بازگشتی [tex]O(\log (n))[/tex] می شودو فضای پشته مورد نیاز هم [tex]O(\log (n))[/tex] خواهد بود . ولی در بدترین حالت اگر داده‌ها مرتب شده باشند که در این صورت داده‌ها به دو قسمت [tex]n-1[/tex] و قسمت دیگر با اندازه صفر تقسیم می شوند آنگاه حداکثر فضای پشته مورد نیاز [tex]O(n)[/tex] خواهد بود .

ارسال:
  

sal_dovomi پاسخ داده:

RE: حداکثر فضای پشته مورد نیاز برای اجرای الگوریتم QuickSort ؟

(۲۸ دى ۱۳۸۹ ۱۰:۱۸ ب.ظ)parsaNA نوشته شده توسط:  با سلام.
حداکثر فضا اگر هر بار داده‌ها به طور مساوی تقسیم بشوند حداکثر عمق درخت بازگشتی [tex]O(\log (n))[/tex] می شودو فضای پشته مورد نیاز هم [tex]O(\log (n))[/tex] خواهد بود . ولی در بدترین حالت اگر داده‌ها مرتب شده باشند که در این صورت داده‌ها به دو قسمت [tex]n-1[/tex] و قسمت دیگر با اندازه صفر تقسیم می شوند آنگاه حداکثر فضای پشته مورد نیاز [tex]O(n)[/tex] خواهد بود .

این [tex]lgn[/tex]
که گفتین میشه تعداد مرتبه تقسیم شدن.خوب در هر مرحله هم یه آرایه n عنصری داریم پس میشه [tex]nlgn[/tex]
میشه اگه اشتباهه تصحیح کنین؟
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

حامد پاسخ داده:

RE: حداکثر فضای پشته مورد نیاز برای اجرای الگوریتم QuickSort ؟

در تکمیل مطالبی که نفر قبلی عنوان نمودند:
برای لیستهای بزرگ ما دیگر نمی تونیم فضایی که متغییرهای Left و Right در اختیار میگیرند را در نظر نگیریم برای همین [tex]O(lgn)[/tex] نیز برای این مورد باید در نظر گرفت و در واقعیت فضای پشته در حالت متوسط یا بهترین حالت برابر میشه با [tex]O(lg^2n)[/tex] و در بدترین حالت برابر میشه با [tex]O(nlgn)[/tex] .

ارسال:
  

parsaNA پاسخ داده:

RE: حداکثر فضای پشته مورد نیاز برای اجرای الگوریتم QuickSort ؟

(۲۹ دى ۱۳۸۹ ۰۲:۵۲ ق.ظ)حامد نوشته شده توسط:  در تکمیل مطالبی که نفر قبلی عنوان نمودند:
برای لیستهای بزرگ ما دیگر نمی تونیم فضایی که متغییرهای Left و Right در اختیار میگیرند را در نظر نگیریم برای همین [tex]O(lgn)[/tex] نیز برای این مورد باید در نظر گرفت و در واقعیت فضای پشته در حالت متوسط یا بهترین حالت برابر میشه با [tex]O(lg^2n)[/tex] و در بدترین حالت برابر میشه با [tex]O(nlgn)[/tex] .

حامد جان از کدم کتاب گفتی این جمله رو . من از رو مقسمی گغتم .
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

parsaNA پاسخ داده:

حداکثر فضای پشته مورد نیاز برای اجرای الگوریتم QuickSort ؟

این عین متن کتاب مقسمیه .
من با جواب حامد مردد شدم . خودمم نمی دونم

ارسال:
  

حامد پاسخ داده:

RE: حداکثر فضای پشته مورد نیاز برای اجرای الگوریتم QuickSort ؟

(۰۲ بهمن ۱۳۸۹ ۰۱:۲۰ ب.ظ)parsaNA نوشته شده توسط:  من با جواب حامد مردد شدم . خودمم نمی دونم
بهتره همون کتابهای کنکوری را مبنا قرار بدهید.فکر نمی کنم که در این حد به جزییات توی سوالات کنکور توجه بشه.اگر با جوابم شما رو مردد کردم واقعا شرمندم.
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  راهنمایی در مورد تعریف محیط عملیاتی داروخانه برای آز پایگاه داده ngmsshd ۲ ۷,۹۸۷ ۰۴ اردیبهشت ۱۴۰۲ ۰۵:۲۹ ب.ظ
آخرین ارسال: Eris_mw
  استفاده از پشته armiii ۰ ۱,۰۹۵ ۰۳ دى ۱۴۰۰ ۱۲:۴۳ ق.ظ
آخرین ارسال: armiii
  در نوشتن چند جمله انگلیسی نیاز به کمک دارم fa_karoon ۰ ۱,۶۸۷ ۰۳ شهریور ۱۴۰۰ ۰۱:۰۹ ب.ظ
آخرین ارسال: fa_karoon
  به کتاب های کنکور ارشد کامپیوتر نیاز دارم Dermobd ۰ ۲,۳۹۰ ۰۵ آذر ۱۳۹۹ ۰۳:۳۳ ب.ظ
آخرین ارسال: Dermobd
  چگونه این خطا را موقع اجرای sql server 2014 رفع کنم ؟ farahnaz ۲ ۳,۰۳۱ ۱۹ مهر ۱۳۹۹ ۰۲:۱۸ ق.ظ
آخرین ارسال: farahnaz
  اجرای نرم افزار ویندوز در اندروید elecomco ۰ ۳,۰۵۵ ۰۴ خرداد ۱۳۹۹ ۰۸:۳۷ ب.ظ
آخرین ارسال: elecomco
  نیاز به دیتا ست jaroon ۷۲ ۶۰,۱۸۳ ۱۷ فروردین ۱۳۹۹ ۱۰:۴۳ ب.ظ
آخرین ارسال: manam1234
  راهنمایی در مورد محلی امن برای زندگی نزدیک چهارراه ولیعصر kadoos ۹ ۷,۹۲۴ ۱۴ اسفند ۱۳۹۸ ۱۱:۰۰ ب.ظ
آخرین ارسال: ehsan0000
  یادگیری برنامه نویسی تا اجرای پروژه های بزرگ The BesT ۳ ۳,۶۱۹ ۱۲ آذر ۱۳۹۸ ۰۳:۵۸ ب.ظ
آخرین ارسال: marvelous
  شبکه عصبی مک کلاچ برای یک مورد کاربردی با متلب Sanazzzz.mi ۰ ۲,۲۱۴ ۲۶ مهر ۱۳۹۸ ۰۱:۲۰ ق.ظ
آخرین ارسال: Sanazzzz.mi

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close