صفحه‌ها: ۱ ۲
سلام.
دوستان تفاوت این دو تست چی هست؟؟
![[تصویر: 151099_1_1379086801.jpg]](https://img.manesht.ir/151099_1_1379086801.jpg)
برام خیلی سواله! ٥٩ رو زده گزینه ۱ اما ٦٠ رو زده ۴!!
Sent from my Google Galaxy Nexus using Tapatalk 2.4
سلام . این دو تا تست یه مدت فکر من رو هم مشغول کرده بودند. هنوز هم نمیدونم درست فهمیدم یا نه!!!
تو پاسخنامه گفته : در سوال ۵۹ فرم خود تابع داده شده اما توی سوال ۶۰ فرم پیچیدگی تابع و این دو همیشه مثل هم نیستند!
پس در سوال ۶۰ نمیتونیم از ترسیم درخت بازگشتی و شمارش گره ها استفاده کنیم . سوال ۶۰ رو با جایگذاری حل کرده
این چیزی بود که من خوندم ولی هنوز هم خودم اشکال دارم.
آره. اما منم نمیدونم چه زمانی باید تعداد گره‌ها شمرده شه و چه موقع باید برای هر گره مقداری که جمع میشه باهاش رو هم حساب کرد!
سلام .
برای تست اولی خود تابع رو بهت داده و خواسته T رو بدست بیاری (زمان الگوریتم تابع F رو به دست بیاورید یعنی اون n که با تابع F جمع شده خروجی محاسبات داخلی تابع بازگشتی است نه سربار زمانی) که میشه [tex]O(n)[/tex]
برای دومی باید توجه داشت که همون طوری که صورت تست گفته شده تابع بازگشتی زمانی یا همون T رو بهت داده یعنی اون n که با تابع T جمع شده سربار زمانی به ازای هر بار اجرای تابع است و باید محاسبه کنی که میشه همون [tex]O(n^{2})[/tex]
ممنون جاوا جان.
پس نتیجه اینکه توی جاهایی که تابع داده، توی درخت باید فقط تعداد گره‌ها رو بشماریم، فارق از اینکه آخرش با چه چیزی جمع میشه.
اما توی جاهایی که رابطه بازگشتی داده، باید برای هر سطر از درخت اون مقداری که جمع میشه رو حساب کرد و به اندازه‌ی ارتفاع با هم جمع کرد.
پیرو فرمایشات دوست خوبم اقای mp1368 اینم بگم که اولی هر فراخوانی یک واحد زمانی حساب میشه و بدون در نظر گرفتن متغیرn ،تابع زمانی این الگوریتم در واقع f(n-1)+1 هست . یعنی یک بار الان فراخوانی شده(تابع در حال اجرا) و دوباره با مقدار n-1 هم فراخونی بشه!!!
میشه لطف کنید در ادامه جواب اینها رو هم بگید؟
T(n)= T(n-1) + Lg n
و
T(n)= 2T(n-1) + Lg n
توی اولی حاصل سطر اول میشه Log n-1، سطر بعد Log n-2 و ... میرسه به Log 1. پس در نهایت جواب میشه سیگما Log i برای i از ۱ تا n. درسته؟ اما جواب صحیح رو زده O(nLgn)x.
ممنون از لطفت.
در تست اول زمان اجرایی تابع رو خواسته. دقت کن که معنیش میشه چند بار تابع اجرا میشه؟؟؟ وقتی که ازت میپرسه چند بار تابع داره اجرا میشه دیگه n رو چرا در نظر بگیری؟؟ مثل این میمونه بهت بگن تو چند ساعت درس خوندی؟ بگی من ۴ ساعت خوندم و توی هر ساعت ۱۰ صفحه.(۱۰ رو همون n فرض کن) . بعد بگی پس من ۴*۱۰ = ۴۰ ساعت درس خوندم!!!!!!
در تست دوم تابع زمان رو داده نه تابع مسئله. یعنی اصلا مسئله یه چیزی دیگه بوده حالا تابع زمانش شده این. اینجا n تاثیر گذاره. مثال اینجا این میشه که بهت میگن چند ساعت درس خوندی؟ میگی ۱۰ صفحه خوندم(این ۱۰ همون n میشه) هر صفحه ۱ ساعت طول کشیده پس ۱*۱۰=۱۰ ساعت خوندم.
(۰۹ دى ۱۳۹۱ ۰۹:۵۸ ب.ظ)Amir V نوشته شده توسط: میشه لطف کنید در ادامه جواب اینها رو هم بگید؟درسته دیگه جواب صحیح همون nlgn هست چون log ها در هر پایه و هر مقداری که داشته باشند با هم هم رشد هستند و میتونیم همشون رو lgn در نظر بگیریم که در کل میشه nlgn .
T(n)= T(n-1) + Lg n
و
T(n)= 2T(n-1) + Lg n
توی اولی حاصل سطر اول میشه Log n-1، سطر بعد Log n-2 و ... میرسه به Log 1. پس در نهایت جواب میشه سیگما Log i برای i از ۱ تا n. درسته؟ اما جواب صحیح رو زده O(nLgn)x.
ممنون از لطفت.
درسته... مرسی.
اون دومی هم میشه ۲ به توان Lg n اره؟
و این هم آخریش:
T(n)=T(n/2)+T(n/4)+T(n/8)+n
ممنون میشم اینو هم جواب بدید.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
سلام
خیلی جالب شد!
تو کتاب شما سوال مربوط به دولتی ۷۴ و آزاد ۸۴ رو مشابه فرض کرده
ولی آقای یوسفی تو کتاب ساختمان سوال دولتی ۷۴ رو زده و گفته از مرتبه n هست
ولی تو طراحی الگوریتم آزاد ۸۴ رو زده و گفته از مرتبه n*2!!!
چه سریع جواب دادن بچه ها
یه قسمتی رو پاک کردم دیگه!
(۰۹ دى ۱۳۹۱ ۰۹:۵۸ ب.ظ)Amir V نوشته شده توسط: میشه لطف کنید در ادامه جواب اینها رو هم بگید؟
T(n)= T(n-1) + Lg n
و
T(n)= 2T(n-1) + Lg n
توی اولی حاصل سطر اول میشه Log n-1، سطر بعد Log n-2 و ... میرسه به Log 1. پس در نهایت جواب میشه سیگما Log i برای i از ۱ تا n. درسته؟ اما جواب صحیح رو زده O(nLgn)x.
ممنون از لطفت.
اولی رو اینجور ببین. قراره T(n) چند بار اجرا شه؟ هر مرحله یکی از n کم میشه یعنی n بار داره اجرا میشه و در هر بار lgn زمان میبره. که میشه nlgn
زمان دومی هم میشه این؟ [tex](2^n)\log n[/tex]
(۰۹ دى ۱۳۹۱ ۱۰:۱۷ ب.ظ)asusx59sr نوشته شده توسط:دومی به نظرم میشه ۲ به توان lgn.(09 دى ۱۳۹۱ ۰۹:۵۸ ب.ظ)Amir V نوشته شده توسط: میشه لطف کنید در ادامه جواب اینها رو هم بگید؟
T(n)= T(n-1) + Lg n
و
T(n)= 2T(n-1) + Lg n
توی اولی حاصل سطر اول میشه Log n-1، سطر بعد Log n-2 و ... میرسه به Log 1. پس در نهایت جواب میشه سیگما Log i برای i از ۱ تا n. درسته؟ اما جواب صحیح رو زده O(nLgn)x.
ممنون از لطفت.
اولی رو اینجور ببین. قراره T(n) چند بار اجرا شه؟ هر مرحله یکی از n کم میشه یعنی n بار داره اجرا میشه و در هر بار lgn زمان میبره. که میشه nlgn
زمان دومی هم میشه این؟ [tex](2^n)\log n[/tex]
نه ببین این زمان یک درخت به ارتفاع n که هر گره دوتا گر داره تا اینجا میشه [tex]2^n[/tex]
هزینه هر مرحله هم که lgn . پس میشه [tex](2^n)\log n[/tex]
(۰۹ دى ۱۳۹۱ ۱۰:۳۱ ب.ظ)asusx59sr نوشته شده توسط: نه ببین این زمان یک درخت به ارتفاع n که هر گره دوتا گر داره تا اینجا میشه [tex]2^n[/tex]
هزینه هر مرحله هم که lgn . پس میشه [tex](2^n)\log n[/tex]
اهان. من جواب درستو ندارم اما به نظر جواب تو درسته.
این چی میشه؟
T(n)=T(n/2)+T(n/4)+T(n/8)+n