(۱۸ دى ۱۳۹۱ ۱۱:۰۷ ب.ظ)Amir V نوشته شده توسط:  سلام.

دوستان رابطه‌ی [tex]T(n)= 2T(n/2) lgn![/tex] مگر از [tex]O(nLog^2 n)[/tex] نمیشه؟

چون کتاب پارسه نوشته از [tex]O(nLogn)[/tex] میخوام ببینم من اشتباه میکنم یا پارسه!

مرسی.

سلام
اگر فاکتوریل شامل logn شود جواب پارسه درسته ولی اگر فاکتوریل فقط شامل n شود جواب شما درست است. (کجای پارسه نوشته ؟ صفحه چند؟)

به نظرم جواب پارسه درسته!طبق قضیه مستر!

(۱۸ دى ۱۳۹۱ ۱۱:۳۶ ب.ظ)۸Operation نوشته شده توسط:  به نظرم جواب پارسه درسته!طبق قضیه مستر!

قضیه مستر میگه اگه [tex]f(n)=nLog^k n[/tex] ، اون وقت کل مسئله میشه از nLog^(K+1) n

(۱۸ دى ۱۳۹۱ ۱۱:۵۱ ب.ظ)Amir V نوشته شده توسط:  قضیه مستر میگه اگه [tex]f(n)=nLog^k n[/tex] ، اون وقت کل مسئله میشه از nLog^(K+1) n

آخه این یه معادل سازی تقریبی امیرجون!اگه nLog n بود حق با شماست!ولی این نیست!بین معادل سازی مرتیه زمانی با فرمول مستر که واسه لگاریتم نوشتی تفاوت وجود داره!
دوستان دیگه هم نظر بدن!

جواب خودت درسته. با همون استدلالی که خودت تو پست شماره ۵ داشتی.

طبق سوال a و b برابر هستند، پس فرمول مستر

Log1.jpg
اندازه فایل: ۱/۲ KB

می شه و جواب پارسه درست هست.
دوستان دیگه هم نظرشون رو بدن.

سلام
جوابت درسته ،پارسه ممکنه غلط تایپی داشته باشه ومنم توان ۲ موافقم.

(۱۸ دى ۱۳۹۱ ۱۱:۳۶ ب.ظ)۸Operation نوشته شده توسط:  به نظرم جواب پارسه درسته!طبق قضیه مستر!

(۱۹ دى ۱۳۹۱ ۰۶:۰۹ ب.ظ)jafarir نوشته شده توسط:  جوابت درسته ،پارسه ممکنه غلط تایپی داشته باشه ومنم توان ۲ موافقم.

دوستان عزیز من با توجه به کلید سنجش گفتم که پارسه درسته!البته خود پارسه و پوران هم بر اساس همین کلید جواب رو دادن و غلط تایپی نیست!
سوال علوم کامپیوتره ۸۲ هستش!

آخه عین عبارتی که من نوشتم رو توی پارسه نوشته! برای مستر توان لگاریتم +۱ میشه! الان اینجا چرا نشده؟

(۱۹ دى ۱۳۹۱ ۰۶:۴۳ ب.ظ)Amir V نوشته شده توسط:  آخه عین عبارتی که من نوشتم رو توی پارسه نوشته! برای مستر توان لگاریتم +۱ میشه! الان اینجا چرا نشده؟

راست میگی امیر!
الان پارسه چک کردم!
این دو صفحه پارسه کلا همین مدلیه!یعتی استدلال به هدف رسیدنه به جواب کلیده!!!
والا منم موندم چی بگم امیر جون!
ولی من اگه این صفحه رو ندیده بودم می گفتم همون استدلال پست ۶ درسته!اما الان به استلال خودمم شک کردم!!!
از دسته این سوالای مشکوک!

(۱۸ دى ۱۳۹۱ ۱۱:۰۷ ب.ظ)Amir V نوشته شده توسط:  سلام.

دوستان رابطه‌ی [tex]T(n)= 2T(n/2) lgn![/tex] مگر از [tex]O(nLog^2 n)[/tex] نمیشه؟

چون کتاب پارسه نوشته از [tex]O(nLogn)[/tex] میخوام ببینم من اشتباه میکنم یا پارسه!

مرسی.

جواب خودتون درسته.حالا اگر پارسه طور دیگه ای نوشته اشتباه از پارسه است.

(۱۸ دى ۱۳۹۱ ۱۱:۰۷ ب.ظ)Amir V نوشته شده توسط:  سلام.

دوستان رابطه‌ی [tex]T(n)= 2T(n/2) lgn![/tex] مگر از [tex]O(nLog^2 n)[/tex] نمیشه؟

چون کتاب پارسه نوشته از [tex]O(nLogn)[/tex] میخوام ببینم من اشتباه میکنم یا پارسه!

مرسی.

به نظر من هم رابطه شما درسته .

---

پس همگی نتیجه میگیرم که جواب امیر درسته و کلید سنجش اشتباهه....
منم دیگه تابع نظر اکثریت میشم

آقا یه سوال رشد کدوم تابع سریع تره با دلیل. !logn یا !(logn)?

(۰۱ بهمن ۱۳۹۱ ۰۷:۲۹ ب.ظ)mahdiii نوشته شده توسط:  آقا یه سوال رشد کدوم تابع سریع تره با دلیل. !logn یا !(logn)?

!(logn) بیشتره!نجومی هم بیشتره!
lgn! = nlgn
مثال:n=1024
logn!=10240
۳۶۲۸۸۰۰=!(logn)

قضیه ی master اینه :

سوال شما اینه :
[tex]T(n)= 2T(n/2) lgn![/tex]
ببین سمت چپ میشه n به توان لگاریتم ۲ در مبنای ۲ که جواب میشه teta_n
سمت راست هم میشه : teta_nLgn
----
در اینجا حالت خاص رو داریم :
اینجا چون f(n در [tex]lg^k(n)[/tex] ضرب شده ابتدا [tex]lg^k(n)[/tex] رو حذف کن میشه:
سمت چپ میشه o_n
سمت راست هم میشه o_n
چون مساوی شدن پس سمت راست یعنی f(n) رو lgn ضرب می کنی میشه nlgn
---
حالا اون چیزی که حذف کرده بودیم یعنی [tex]lg^k(n)[/tex] رو دوباره درش ضرب کن میشه :
[tex]nlg^{k 1}(n)[/tex]
[tex]nlg^{2}(n)[/tex]
---------
در حالت کلی یک حالت داریم به اسم حالت تعمیم:
[tex]t(n)=aT(\frac{n}{b}) f(n)[/tex]
اگر در روش قضیه ی اصلی داشته باشیم :
[tex]f(n)\varepsilon \theta(n^{log_{b}^{a}})lg^k{n}[/tex]
و k>=0 باشد داریم:
[tex]T(n)\varepsilon \theta(n^{log_{b}^{a}})lg^{k 1}{n}[/tex]
----------------------
مثال :
[tex]T(n)=2t(n/2) nlgn=\theta(nlg^2n)[/tex]
مثال بعدی:
[tex]T(n)=4t(n/2) n^2lgn=\theta(n^2lg^2n)[/tex]

نکته ای که جا گذاشتم هم اینه :
ثابت میشه که lg(n!)=nlgn
---

من جزوه ی طورانی رو که واسه پارسالش هست دارم همین سوال رو حل کرده و جوابش هم همون nlog^2n (به توان ۲) و نمیدونم چرا تو کتابش نوشته nlogn

منم طورانی رو دارم ولی نه واسه پارسال
عکس بگیرید آپلود کنید بدید ببینیم کجا اشکال داره

احتمالا اشتباه تایپی بوده