سلام.
در الگوریتم QuickSort حداکثر فضای پشته مورد نیاز برای اجرای این الگوریتم چه میزان است؟
با سلام.
حداکثر فضا اگر هر بار داده‌ها به طور مساوی تقسیم بشوند حداکثر عمق درخت بازگشتی [tex]O(\log (n))[/tex] می شودو فضای پشته مورد نیاز هم [tex]O(\log (n))[/tex] خواهد بود . ولی در بدترین حالت اگر داده‌ها مرتب شده باشند که در این صورت داده‌ها به دو قسمت [tex]n-1[/tex] و قسمت دیگر با اندازه صفر تقسیم می شوند آنگاه حداکثر فضای پشته مورد نیاز [tex]O(n)[/tex] خواهد بود .
در تکمیل مطالبی که نفر قبلی عنوان نمودند:
برای لیستهای بزرگ ما دیگر نمی تونیم فضایی که متغییرهای Left و Right در اختیار میگیرند را در نظر نگیریم برای همین [tex]O(lgn)[/tex] نیز برای این مورد باید در نظر گرفت و در واقعیت فضای پشته در حالت متوسط یا بهترین حالت برابر میشه با [tex]O(lg^2n)[/tex] و در بدترین حالت برابر میشه با [tex]O(nlgn)[/tex] .
(۲۹ دى ۱۳۸۹ ۰۲:۵۲ ق.ظ)حامد نوشته شده توسط: در تکمیل مطالبی که نفر قبلی عنوان نمودند:
برای لیستهای بزرگ ما دیگر نمی تونیم فضایی که متغییرهای Left و Right در اختیار میگیرند را در نظر نگیریم برای همین [tex]O(lgn)[/tex] نیز برای این مورد باید در نظر گرفت و در واقعیت فضای پشته در حالت متوسط یا بهترین حالت برابر میشه با [tex]O(lg^2n)[/tex] و در بدترین حالت برابر میشه با [tex]O(nlgn)[/tex] .
حامد جان از کدم کتاب گفتی این جمله رو . من از رو مقسمی گغتم .
(۲۹ دى ۱۳۸۹ ۱۲:۴۲ ب.ظ)parsaNA نوشته شده توسط: حامد جان از کدم کتاب گفتی این جمله رو . من از رو مقسمی گغتم .
کتاب خاصی مد نظرم نبود ولی اگر تحقیق کنید در واقعیت اینگونه خواهد بود.
(۲۹ دى ۱۳۸۹ ۰۴:۴۷ ب.ظ)حامد نوشته شده توسط:(29 دى ۱۳۸۹ ۱۲:۴۲ ب.ظ)parsaNA نوشته شده توسط: حامد جان از کدم کتاب گفتی این جمله رو . من از رو مقسمی گغتم .
کتاب خاصی مد نظرم نبود ولی اگر تحقیق کنید در واقعیت اینگونه خواهد بود.
آخه نمی شه که . n هر چقدر هم که بزرگ باشه اگه دادها‌ها پخش باشن می شه [tex]O(2\log n)[/tex] که با [tex]O(\log n)[/tex] برابره و اگه هم اینطور نباشه یعنی داده‌ها مرتب باشند که می شه [tex]O(n)[/tex] . اگه توضیحی دارید بفرمایید .
(۲۹ دى ۱۳۸۹ ۰۶:۳۴ ب.ظ)parsaNA نوشته شده توسط: آخه نمی شه که . n هر چقدر هم که بزرگ باشه اگه دادها‌ها پخش باشن می شه [tex]O(2\log n)[/tex] که با [tex]O(\log n)[/tex] برابره و اگه هم اینطور نباشه یعنی داده‌ها مرتب باشند که می شه [tex]O(n)[/tex] . اگه توضیحی دارید بفرمایید .
منظورتون رو متوجه نمیشم.برای اطمینان میتونید سایتهای زیر را ببینید:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۲۸ دى ۱۳۸۹ ۱۰:۱۸ ب.ظ)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]
میشه اگه اشتباهه تصحیح کنین؟
این عین متن کتاب مقسمیه .
من با جواب حامد مردد شدم . خودمم نمی دونم
(۰۲ بهمن ۱۳۸۹ ۰۱:۲۰ ب.ظ)parsaNA نوشته شده توسط: من با جواب حامد مردد شدم . خودمم نمی دونمبهتره همون کتابهای کنکوری را مبنا قرار بدهید.فکر نمی کنم که در این حد به جزییات توی سوالات کنکور توجه بشه.اگر با جوابم شما رو مردد کردم واقعا شرمندم.
(۰۲ بهمن ۱۳۸۹ ۰۱:۳۸ ب.ظ)حامد نوشته شده توسط:(02 بهمن ۱۳۸۹ ۰۱:۲۰ ب.ظ)parsaNA نوشته شده توسط: من با جواب حامد مردد شدم . خودمم نمی دونمبهتره همون کتابهای کنکوری را مبنا قرار بدهید.فکر نمی کنم که در این حد به جزییات توی سوالات کنکور توجه بشه.اگر با جوابم شما رو مردد کردم واقعا شرمندم.
نه حامد جان، خواهش می کنم، دشمنتون شرمنده . شما بیشتر از من تحقیق کردین . منم فکر می کنم همونی که شما گفتی درست‌تر باشه . به این کتاب های کنکوری هم نمیشه اطمینان کرد .