سراسری علوم کامپیوتر ۹۰ سوال ۸۵
با سلام
کسی درباره این سوال ایده ای داره؟
[tex]T(n)=2T(\frac{n}{2})+\frac{n}{\log(n)}[/tex]
من خودم با استفاده از جایگزاری با تکرار و انتگرال گرفتن نهایتا به این جمله رسیدم:
[tex]\frac{n}{2}\log{n}+\frac{n}{log{n}}[/tex]
و بنابراین نتیجه گرفتم که دارای پیچیدگی زمانی
[tex]O(n\log{n})[/tex]
هستش اما توی پاسخنامه پیچیدگی زمانی رو
[tex]O(n\log{\log{n}})[/tex]
معرفی کرده
کسی نظری نداره؟ راه حل دقیقش رو نمیدونه؟
(۱۳ دى ۱۳۹۶ ۰۷:۲۹ ب.ظ)arman12345 نوشته شده توسط: کسی نظری نداره؟ راه حل دقیقش رو نمیدونه؟سلام.
یکی از راههای حل این سوال استفاده از درخت بازگشت که در نهایت دارای پیچیدگی زمانی[tex]\ O(n\: \log\: \log\: n)[/tex]
(اگه خواستین پیام بدین تا پاسخ تشریحی رو براتون ارسال کنم )البته با جایگزاری با تکرار هم که در واقع همون درخت بازگشت به همین جواب میرسه .فکر کنم اشتباه حل کردین !
(۱۳ دى ۱۳۹۶ ۱۰:۵۰ ب.ظ)Alirezaj نوشته شده توسط:(13 دى ۱۳۹۶ ۰۷:۲۹ ب.ظ)arman12345 نوشته شده توسط: کسی نظری نداره؟ راه حل دقیقش رو نمیدونه؟سلام.
یکی از راههای حل این سوال استفاده از درخت بازگشت که در نهایت دارای پیچیدگی زمانی[tex]\ O(n\: \log\: \log\: n)[/tex]
(اگه خواستین پیام بدین تا پاسخ تشریحی رو براتون ارسال کنم )البته با جایگزاری با تکرار هم که در واقع همون درخت بازگشت به همین جواب میرسه .فکر کنم اشتباه حل کردین !
میشه پاسخ تشریحی رو عکس بگیرید اینجا هم بزارید.ممنون میشیم.
(۱۳ دى ۱۳۹۶ ۰۱:۳۱ ب.ظ)arman12345 نوشته شده توسط: سراسری علوم کامپیوتر ۹۰ سوال ۸۵
با سلام
کسی درباره این سوال ایده ای داره؟
[tex]T(n)=2T(\frac{n}{2})+\frac{n}{\log(n)}[/tex]
(۱۳ دى ۱۳۹۶ ۱۰:۵۰ ب.ظ)Alirezaj نوشته شده توسط:(13 دى ۱۳۹۶ ۰۷:۲۹ ب.ظ)arman12345 نوشته شده توسط: کسی نظری نداره؟ راه حل دقیقش رو نمیدونه؟سلام.
یکی از راههای حل این سوال استفاده از درخت بازگشت که در نهایت دارای پیچیدگی زمانی[tex]\ O(n\: \log\: \log\: n)[/tex]
(اگه خواستین پیام بدین تا پاسخ تشریحی رو براتون ارسال کنم )البته با جایگزاری با تکرار هم که در واقع همون درخت بازگشت به همین جواب میرسه .فکر کنم اشتباه حل کردین !
سلام خیلی ممنون واقعا منو از گیجی نجات دادین. بله راهم درست بود ولی یک اشتباه کوچک داشتم که جواب رو غلط نتیجه می داد. واقعا ممنون
(۱۴ دى ۱۳۹۶ ۱۲:۵۳ ق.ظ)boshbosh نوشته شده توسط:(13 دى ۱۳۹۶ ۰۱:۳۱ ب.ظ)arman12345 نوشته شده توسط: سراسری علوم کامپیوتر ۹۰ سوال ۸۵
با سلام
کسی درباره این سوال ایده ای داره؟
[tex]T(n)=2T(\frac{n}{2})+\frac{n}{\log(n)}[/tex]
از شما هم ممنون که پاسخ تشریحی رو ارسال کردید. اگر اینو نمیدیدم ممکن بود بازم متوجه نشم اشتباهم کجاست و گیج بشم. خیلی خوشحالم جواب سوالمو پیدا کردم.
سلام. خواهش میکنم