با سلام
آیا گزینه ی ۱ درست است؟!!!
چرا ؟
[attachment=12774]
سلام.
من فکر میکنم گزینه ۴ باید درست باشه.
چون برای حذف نود آخری در لیست پیوندی باید تا قبل از نود آخری، لیست پیمایش بشه و اصلا ربطی به دانستن اشاره گرهای ابتدا و انتهایی نداره. حذف از لیستی که در گزینه ۴ اشاره بهش کرده از مرتبه O(n است.
پاسخ : گزینه ۴
بله گزینه ۴ جواب تست هست .
ببخشید من بد سوال پرسیدم . منظورم اینه که گزینه ۱ چرا نمیتونه جواب تست باشه؟ چون رشد فاکتوریا از n^n مگر کمتر نیست؟ اما مساوی زده ، پس این گزینه هم نادرسته دیگه؟!
گزینه ۴ که واضحه چرا نادرسته: برای حذف آخرین عنصر در لیست یک طرفه نیاز به تصحیح اشاره‌گر عنصر قبل آخر داریم که رسیدن به این عنصر نیازمند یک پیمایش با مرتبه‌ی زمانی [tex]\Theta (n)[/tex] هستش.
در مورد گزینه‌ی ۱ هم اگه دقت کنیم که نماد O یک مجموعه رو توصیف میکنه، واضحه که دو مجموعه‌ی [tex]O(n!)[/tex] و [tex]O(n^{n})[/tex] برابر نیستند. به عنوان مثال اگه خود تابع [tex]n^{n}[/tex] رو در نظر بگیریم، چون رشد این تابع از !n خیلی بیشتره، پس این تابع در [tex]O(n!)[/tex] قرار نمیگیره، در حالی در [tex]O(n^{n})[/tex] قرار می‌گیره.
احتمالاً علت اشتباه طراح اینه که سه مجموعه‌ی [tex]O(logn(n!))=O(log(n^{n}))=O(n\cdot logn)[/tex] برابر هستند و طراح اشتباهاً نتیجه گرفته که پس [tex]O(n^{n})=O(n!)[/tex].
متأسفانه طراحانی که برای طرح سؤال کنکور انتخاب میشن با وجود این که اکثراً از استادای معروف ایران هم هستند، ولی سواد و تسلط لازم رو روی درسی که دارند تدریس می‌کنند ندارند! همین موضوع باعث میشه تقریباً هر سال توی فقط همین درس ساختمان داده حداقل ۳-۴ تا سؤال توی رشته‌های مختلف اشتباه باشه!
از معمول‌ترین اشتباهات توی مبحث پیچیدگی زمانی اینه که طراح حتی تفاوت نماد [tex]O[/tex] رو با نماد [tex]\Theta[/tex] درک نکرده و این دوتا رو جای هم به کار میبره! یا مثلاً توی همین تست، طراح دقت نکرده که نماد O داره یک مجموعه رو نشون میده و استفاده از علامت < و > برای مجموعه معنی نمیده (گزینه‌ی ۲) و باید از علامت زیرمجموعه استفاده بشه!
به نظر من گزینه ۴ درسته (یعنی پاسخ سوال نیست) چون با داشتن اشاره گر last دیگه نیازی به پیمایش لیست نیست و حذف عنصر آخر از مرتبه بیگ او یک میشه!
دوست عزیز گزینه یک هم نادرسته و نمیشه اینجا این دو تا رو برابر دونست!!!