(۲۲ بهمن ۱۳۹۲ ۱۲:۳۷ ق.ظ)hosshah نوشته شده توسط:  به نظرم جایگذاری موقعی خوبه که تو گزینه ها رابطه رو داریم نه مرتبه رو. تازه اون هم مرتبه O که اصلا نمیتونه تخمین دقیقی باشه

مثلا برای سوال اول اگرچه فک کنم شما گفتی nlogn جوابه من مثل زیر حل کردم و به جواب n رسیدم که کلید هم همونو زده بود:
من گفتم از n تا عددمون logn تا عدد داریم (۲، ۴، ۸ و ...) که log روز مصرفشون طول میکشه.
از n-logn عدد باقی مونده حدودا (تاکیدم روی حدودا هستش چون خیلی دقت لازم نداریم) (n-logn) تقسیم بر ۲ عدد زوج داریم که تقریبا ۲ مرجله خوردنشون طول میکشه و n-logn تقسیم بر ۲ عدد فرد داریم که با یه مرحله تموم میشن
[tex](\log n\times\log n) (((n-\log n)\div2)\times2) (((n-\log n)\div2)\times1)=\frac{3n}{2} \log^2n-\frac{3\log n}{2}\in O(n)[/tex]

حالا نمیدونم این روش رو تا چه حد قبول دارین ولی کلا نظرم اینه که در مورد مرتبه ها از جاگذاری استفاده نکنید

(۲۲ بهمن ۱۳۹۲ ۱۲:۳۰ ق.ظ)El@he نوشته شده توسط:  خب باید تا nهای خیلی بزرگ پیش بریم ولی وقتی سخته من معمولا چندبار تریس میکنم تا روندش دستم بیاد، بعد یه رابطه ی بازگشتی واسش درمیارم و اونو حل میکنم. وگرنه اینکه چون ۷ شده nlogn باشه به نظرم درست نیست، مگر تصادفی! چون اصلا بحث O هستش...
مثلا یه سوال ساختمان ۹۱ کامپیوتر بود فکر کنم، یه نوع ساختار داده بود که از چند مجموعه تشکیل شده بود و ... اونو اگه میخواستی با عددگذاری بری یادمه که اشتباه درمیومد. باید باتوجه به روندش، رابطه مینوشتی.

(۲۲ بهمن ۱۳۹۲ ۱۲:۳۷ ق.ظ)hosshah نوشته شده توسط:  به نظرم جایگذاری موقعی خوبه که تو گزینه ها رابطه رو داریم نه مرتبه رو. تازه اون هم مرتبه O که اصلا نمیتونه تخمین دقیقی باشه

مثلا برای سوال اول اگرچه فک کنم شما گفتی nlogn جوابه من مثل زیر حل کردم و به جواب n رسیدم که کلید هم همونو زده بود:
من گفتم از n تا عددمون logn تا عدد داریم (۲، ۴، ۸ و ...) که log روز مصرفشون طول میکشه.
از n-logn عدد باقی مونده حدودا (تاکیدم روی حدودا هستش چون خیلی دقت لازم نداریم) (n-logn) تقسیم بر ۲ عدد زوج داریم که تقریبا ۲ مرجله خوردنشون طول میکشه و n-logn تقسیم بر ۲ عدد فرد داریم که با یه مرحله تموم میشن
[tex](\log n\times\log n) (((n-\log n)\div2)\times2) (((n-\log n)\div2)\times1)=\frac{3n}{2} \log^2n-\frac{3\log n}{2}\in O(n)[/tex]

حالا نمیدونم این روش رو تا چه حد قبول دارین ولی کلا نظرم اینه که در مورد مرتبه ها از جاگذاری استفاده نکنید

(۲۲ بهمن ۱۳۹۲ ۱۲:۱۳ ق.ظ)masoud67 نوشته شده توسط:  سلام
قصدم از این سوال حل این دوتا مثال نیست ، و فقط میخوام یه موضوعی را بفهمم

تو این سوال خرس ما گفته از مرتبه n روز زنده می مونه


حالا ما میدیم n=4 که میشه ۷ روز واسه زنده موندن خرس . و به نظر میاد بشه nlogn
حالا ما اگه n=8 بدیم تعداد روز زنده موندن خرس میشه ۱۵ روز و اینجا دیگه nlogn نمیشه


و حالا یه مدل بدتر
اینجا جواب میشه nlogn
ولی وقتی عدد گذاری میکنیم واضحه که بیشتر از nlogn میشه .
مثلا به ازای n=2 حدود ۲۱ مرتبه اجرا میشه
و برای n=8 حدود ۶۰ مرتبه اجرا میشه که با nlogn اختلاف زیادی داره


توی مثالهای قبلی به ازای nهای بزرگ مقداری که بدست میاد با مرتبه ای که در نظر میگیریم تناسب برقرار میشه ولی تو این جور مسائل به ازای nهای کوچک ممکنه جواب غلط را بدست بیاریم
اما سوال: آیا اینگونه سوالات تیپ خاصی دارند که معلوم باشه نباید با جایگذاری حل کرد ؟
چون اغلب مسائلی که راه حل برای حل کردنش نداریم و یا سخته سعی میکنیم از جایگذاری استفاده کنیم ، ولی ممکنه این جایگذاری به قیمت یک تست اشتباه تموم بشه

(۲۲ بهمن ۱۳۹۲ ۱۲:۲۹ ق.ظ)ka arman نوشته شده توسط:  من خودم سوالایی رو که تتا و O , ... ازین جور چیزا ندارن رو با جایگذاری حل می کنم و بقیه رو هم با روشهای دیگه مثل قضیه اصلی و ... .

(۲۲ بهمن ۱۳۹۲ ۱۲:۳۱ ق.ظ)masoud67 نوشته شده توسط:  

(22 بهمن ۱۳۹۲ ۱۲:۲۹ ق.ظ)ka arman نوشته شده توسط:  من خودم سوالایی رو که تتا و O , ... ازین جور چیزا ندارن رو با جایگذاری حل می کنم و بقیه رو هم با روشهای دیگه مثل قضیه اصلی و ... .

یعنی میگید با دیدن تتا و O و ... از خیر خطر جایگذاری بگذریم ؟

(۲۲ بهمن ۱۳۹۲ ۱۲:۱۳ ق.ظ)masoud67 نوشته شده توسط:  سلام
قصدم از این سوال حل این دوتا مثال نیست ، و فقط میخوام یه موضوعی را بفهمم

تو این سوال خرس ما گفته از مرتبه n روز زنده می مونه


حالا ما میدیم n=4 که میشه ۷ روز واسه زنده موندن خرس . و به نظر میاد بشه nlogn
حالا ما اگه n=8 بدیم تعداد روز زنده موندن خرس میشه ۱۵ روز و اینجا دیگه nlogn نمیشه


و حالا یه مدل بدتر
اینجا جواب میشه nlogn
ولی وقتی عدد گذاری میکنیم واضحه که بیشتر از nlogn میشه .
مثلا به ازای n=2 حدود ۲۱ مرتبه اجرا میشه
و برای n=8 حدود ۶۰ مرتبه اجرا میشه که با nlogn اختلاف زیادی داره


توی مثالهای قبلی به ازای nهای بزرگ مقداری که بدست میاد با مرتبه ای که در نظر میگیریم تناسب برقرار میشه ولی تو این جور مسائل به ازای nهای کوچک ممکنه جواب غلط را بدست بیاریم
اما سوال: آیا اینگونه سوالات تیپ خاصی دارند که معلوم باشه نباید با جایگذاری حل کرد ؟
چون اغلب مسائلی که راه حل برای حل کردنش نداریم و یا سخته سعی میکنیم از جایگذاری استفاده کنیم ، ولی ممکنه این جایگذاری به قیمت یک تست اشتباه تموم بشه

(۲۲ بهمن ۱۳۹۲ ۱۲:۴۱ ق.ظ)masoud67 نوشته شده توسط:  چرا سفسطه میکنی من کی گفتم nlogn جوابه؟ گفتم وقتی مقدارگذاری با n کوچیک انجام میدی به نظر میاد nlogn جواب باشه

(۲۲ بهمن ۱۳۹۲ ۱۲:۵۳ ق.ظ)hosshah نوشته شده توسط:  اینقدر پوران خوندی شبیه هادی یوسفی شدیا
همش دوست داری نکته در بیاری
قبول دارم حرفاتو

(۲۲ بهمن ۱۳۹۲ ۰۱:۰۳ ق.ظ)hnarghani نوشته شده توسط:  ااینجا من راه حل دکتر ابراهمیم مقدم را میزارم.برای همین سوال یک حلقه while و شرطش اینکه تا موقعه ای n>0باشد خرس زنده میمونه.ابتدا select میکنه یک قطعه رو اگه قطعه فرد باشه یکی از کل کم میکنه و اگه زوج باشه به عنوان یک قطعه کامل اونو در نظر میگیریم .حال میشه یک حلقه while که مرتبش میشه nهمون گزینه یک درسته.

(۲۲ بهمن ۱۳۹۲ ۰۱:۰۸ ق.ظ)masoud67 نوشته شده توسط:  hosshah تحویل بگیر. وقتی میای سفسطه میکنی، بقیه هم میان مثالو حل میکنن. ولی به متن سوال نگاه نمیکنن

(۲۲ بهمن ۱۳۹۲ ۰۱:۱۰ ق.ظ)hosshah نوشته شده توسط:  

(22 بهمن ۱۳۹۲ ۰۱:۰۸ ق.ظ)masoud67 نوشته شده توسط:  hosshah تحویل بگیر. وقتی میای سفسطه میکنی، بقیه هم میان مثالو حل میکنن. ولی به متن سوال نگاه نمیکنن

نه بابا من خواستم مثال بزنم که ما اگه قراره از جایگذاری استفاده نکنیم اینجوری تحلیل کردنم یه راهشه

(۲۲ بهمن ۱۳۹۲ ۰۱:۱۰ ق.ظ)hosshah نوشته شده توسط:  

(22 بهمن ۱۳۹۲ ۰۱:۰۸ ق.ظ)masoud67 نوشته شده توسط:  hosshah تحویل بگیر. وقتی میای سفسطه میکنی، بقیه هم میان مثالو حل میکنن. ولی به متن سوال نگاه نمیکنن

نه بابا من خواستم مثال بزنم که ما اگه قراره از جایگذاری استفاده نکنیم اینجوری تحلیل کردنم یه راهشه