۰
subtitle
ارسال: #۱
دو تست از پیچیدگی زمانی
سلام.
دوستان تفاوت این دو تست چی هست؟؟
![[تصویر: 151099_1_1379086801.jpg]](https://img.manesht.ir/151099_1_1379086801.jpg)
برام خیلی سواله! ٥٩ رو زده گزینه ۱ اما ٦٠ رو زده ۴!!
Sent from my Google Galaxy Nexus using Tapatalk 2.4
دوستان تفاوت این دو تست چی هست؟؟
برام خیلی سواله! ٥٩ رو زده گزینه ۱ اما ٦٠ رو زده ۴!!
Sent from my Google Galaxy Nexus using Tapatalk 2.4
۲
ارسال: #۲
RE: دو تست از پیچیدگی زمانی
سلام .
برای تست اولی خود تابع رو بهت داده و خواسته T رو بدست بیاری (زمان الگوریتم تابع F رو به دست بیاورید یعنی اون n که با تابع F جمع شده خروجی محاسبات داخلی تابع بازگشتی است نه سربار زمانی) که میشه [tex]O(n)[/tex]
برای دومی باید توجه داشت که همون طوری که صورت تست گفته شده تابع بازگشتی زمانی یا همون T رو بهت داده یعنی اون n که با تابع T جمع شده سربار زمانی به ازای هر بار اجرای تابع است و باید محاسبه کنی که میشه همون [tex]O(n^{2})[/tex]
برای تست اولی خود تابع رو بهت داده و خواسته T رو بدست بیاری (زمان الگوریتم تابع F رو به دست بیاورید یعنی اون n که با تابع F جمع شده خروجی محاسبات داخلی تابع بازگشتی است نه سربار زمانی) که میشه [tex]O(n)[/tex]
برای دومی باید توجه داشت که همون طوری که صورت تست گفته شده تابع بازگشتی زمانی یا همون T رو بهت داده یعنی اون n که با تابع T جمع شده سربار زمانی به ازای هر بار اجرای تابع است و باید محاسبه کنی که میشه همون [tex]O(n^{2})[/tex]
۲
ارسال: #۳
RE: دو تست از پیچیدگی زمانی
سلام .
این دو تا سوالی که در ادامه پرسیدی سوال های جالبی هستن که دوستان با تحلیلشون هم یه جور دست گرمی هستش و هم میتونن نتایج جالب و جدیدی رو کسب کنن.
سوال اول
که فک کنم من در آوردی بوده
چون من ندیدم همچین T رو توی تست ها و تمرینها فقط یه جایی این سوال رو دیدم اونم توی مقاله ی خارجی بود که یه الگوریتم ابداعی روی Max-Heap داشت که T الگوریتم همین میشد ولی در کل جالبه و البته دارای ابهام .
اول به این مسئله زیر که امیر جان خودتم به درستی حلش کردی نگاهی بندازیم چون در ادامه به دردمون میخوره
طبق قضیه ای که توی کتاب CLRS بهش اشاره شده با استفاده از تقریب استرلینگ(کتاب الگوریتم محاسبات دانشگاه MIT این تقریب رو کامل توضیح داده) میتونیم بگیم که چون تفاوت لگاریتم ها اونقدری نیست که در تابع اثر بزاره و ما چون داریم به صورت حدی نیز کار میکنیم پس میتونیم در واقع فرض کنیم که همه ی لگاریتم ها همون logn هستند که میشه n تا logn که باعث میشه تساوی [tex]{\color{Red} logn!=\theta (nlogn)}[/tex] درست باشه.
حالا این دوستمون که گفتن جواب [tex]2^{n}\log n[/tex] تقریبا با اثباتی که در زیر میارم و با توجه به نکته ی بالا درست گفتن ولی در ادامه میبینیم که اینم شاید جواب درست نباشه
اثبات اول درخت بازگشت :
اگر بخوایم از طریق درخت بازگشت حل کنیم هزینه هر سطح درخت به صورت زیر محاسبه میشه :
خب حالا جمع کردن این هزینه ها یه کم کار سختیه چون لگاریتم ها با هم متفاوت هستن . ولی اگر از همون قضیه تقریب استرلینگ استفاده کنیم میتونیم فرض کنیم که مسئله به صورت زیر جمع میشه :
همون طوری که میبینیم اینجا نیز فرض کردیم که همه ی لگاریتم ها برابر هستند که باعث میشه فرض کنیم [tex]2^{n}[/tex] تا [tex]logn[/tex] داریم که جواب میشه [tex]\theta (2^{n}\log n)[/tex]
اثبات دوم معادله مشخصه :
روش دوم که بر اساس معادله مشخصه ناهمگن هستش باعث میشه که یه جورایی اثبات اول زیر سوال بره.
برای حل این معادله به این روش یه کم کار سخته ولی با محاسبه T های زیر که حد پایین و بالای مسئله رو محاسبه میکنه ما رو کمک میکنه .
برای این دو تا مثال شرایط اولیه رو ۱ فرض میکنیم :
خب در اینجا ما حد پایین و بالای مسئله رو اثبات کردیم که از مرتبه ی [tex]\theta (2^{n})[/tex] پس در نتیجه مسئله ما هم باید از همین مرتبه باشه
سوال دوم
واسه این معادله مشخصه کاربرد نداره چون با تغییر متغیر [tex]n=2^{m}[/tex] داریم
خب میریم سراغ روش دوم یعنی درخت بازگشت و هزینه سطوح درخت به صورت زیر است
[tex]{\color{Red} (n \frac{n7}{8} \frac{n63}{64} ...)}[/tex]
اینجا کار یه کم سخته ولی باز یه قاعده هستش که ما رو کمک میکنه این قاعده رو در CLRS بهش اشاره شده و فک کنم آقای یوسفی هم بهش اشاره کرده :
[tex](\frac{1}{2} \frac{1}{4} \frac{1}{8} \frac{1}{16} ...) = c[/tex]
این قضیه داره میگه که جمع این سری همیشه یه عدد ثابت میشه و این باعث میشه که سری زیر به این صورت حل بشه
[tex]n \frac{n}{2} \frac{n}{4} \frac{n}{8} ...= n(1 \frac{1}{2} \frac{1}{4} \frac{1}{8} \frac{1}{16} ...) = nc=\theta (n)[/tex]
حواسمون باشه که این با سری [tex]n(1 \frac{1}{2} \frac{1}{3} \frac{1}{4} \frac{1}{5} ...) = \theta (nlogn)[/tex] تفاوت داره چون سری اعداد اینجا خیلی بزرگتر هستش
و در ادامه اگر به سری اعداد خودمون توجه کنیم میبینیم که از سری اعداد [tex]\frac{1}{2} \frac{1}{4} \frac{1}{16} \frac{1}{32} ... [/tex] خیلی کوچیکتره و
این دو تا سوالی که در ادامه پرسیدی سوال های جالبی هستن که دوستان با تحلیلشون هم یه جور دست گرمی هستش و هم میتونن نتایج جالب و جدیدی رو کسب کنن.
سوال اول
[tex]{\color{Red} T(n)=2T(n-1) logn}[/tex]
که فک کنم من در آوردی بوده
چون من ندیدم همچین T رو توی تست ها و تمرینها فقط یه جایی این سوال رو دیدم اونم توی مقاله ی خارجی بود که یه الگوریتم ابداعی روی Max-Heap داشت که T الگوریتم همین میشد ولی در کل جالبه و البته دارای ابهام . اول به این مسئله زیر که امیر جان خودتم به درستی حلش کردی نگاهی بندازیم چون در ادامه به دردمون میخوره
[tex]{\color{Red} T(n)=T(n-1) logn\Rightarrow }[/tex]
[tex]T(n-2) log(n-1) logn.....=... log(n-1) logn= {\color{Red} log(n!)=\theta (nlogn)}[/tex]
[tex]T(n-2) log(n-1) logn.....=... log(n-1) logn= {\color{Red} log(n!)=\theta (nlogn)}[/tex]
طبق قضیه ای که توی کتاب CLRS بهش اشاره شده با استفاده از تقریب استرلینگ(کتاب الگوریتم محاسبات دانشگاه MIT این تقریب رو کامل توضیح داده) میتونیم بگیم که چون تفاوت لگاریتم ها اونقدری نیست که در تابع اثر بزاره و ما چون داریم به صورت حدی نیز کار میکنیم پس میتونیم در واقع فرض کنیم که همه ی لگاریتم ها همون logn هستند که میشه n تا logn که باعث میشه تساوی [tex]{\color{Red} logn!=\theta (nlogn)}[/tex] درست باشه.
حالا این دوستمون که گفتن جواب [tex]2^{n}\log n[/tex] تقریبا با اثباتی که در زیر میارم و با توجه به نکته ی بالا درست گفتن ولی در ادامه میبینیم که اینم شاید جواب درست نباشه
اثبات اول درخت بازگشت :
اگر بخوایم از طریق درخت بازگشت حل کنیم هزینه هر سطح درخت به صورت زیر محاسبه میشه :
[tex]log(n) 2log(n-1) 4log(n-2) 8log(n-3) 16log(n-4) .....[/tex]
خب حالا جمع کردن این هزینه ها یه کم کار سختیه چون لگاریتم ها با هم متفاوت هستن . ولی اگر از همون قضیه تقریب استرلینگ استفاده کنیم میتونیم فرض کنیم که مسئله به صورت زیر جمع میشه :
[tex]log(n) 2log(n-1) 4log(n-2) 8log(n-3) 16log(n-4) .....\Rightarrow[/tex]
[tex]{\color{Red} 2^{n}-1(logn)\Rightarrow 2^{n}logn-logn =\theta(2^{n}logn)}[/tex]
[tex]{\color{Red} 2^{n}-1(logn)\Rightarrow 2^{n}logn-logn =\theta(2^{n}logn)}[/tex]
همون طوری که میبینیم اینجا نیز فرض کردیم که همه ی لگاریتم ها برابر هستند که باعث میشه فرض کنیم [tex]2^{n}[/tex] تا [tex]logn[/tex] داریم که جواب میشه [tex]\theta (2^{n}\log n)[/tex]
اثبات دوم معادله مشخصه :
روش دوم که بر اساس معادله مشخصه ناهمگن هستش باعث میشه که یه جورایی اثبات اول زیر سوال بره.
برای حل این معادله به این روش یه کم کار سخته ولی با محاسبه T های زیر که حد پایین و بالای مسئله رو محاسبه میکنه ما رو کمک میکنه .
برای این دو تا مثال شرایط اولیه رو ۱ فرض میکنیم :
[tex]{\color{Red} T(n)=2T(n-1) 1\Rightarrow} \alpha _{n}-2\alpha _{n-1}-1\Rightarrow 2^{n} \alpha = \theta (2^{n})[/tex]
[tex]{\color{Red} T(n)=2T(n-1) n\Rightarrow} \alpha _{n}-2\alpha _{n-1} =n \Rightarrow 2^{n} n = \theta (2^{n})[/tex]
[tex]{\color{Red} T(n)=2T(n-1) n\Rightarrow} \alpha _{n}-2\alpha _{n-1} =n \Rightarrow 2^{n} n = \theta (2^{n})[/tex]
خب در اینجا ما حد پایین و بالای مسئله رو اثبات کردیم که از مرتبه ی [tex]\theta (2^{n})[/tex] پس در نتیجه مسئله ما هم باید از همین مرتبه باشه
سوال دوم
[tex]T(n)=T(\frac{n}{2}) T(\frac{n}{4}) T(\frac{n}{8}) n[/tex]
واسه این معادله مشخصه کاربرد نداره چون با تغییر متغیر [tex]n=2^{m}[/tex] داریم
[tex]T(2^{m})=T(2^{m-1}) T(2^{m-2}) T(2^{m-3}) 2^{m} \Rightarrow[/tex]
[tex]F(m)=F(m-1) F(m-2) F(m-3) m \Rightarrow[/tex]
حالا معادله قسمت همگن این عبارت به صورت زیر هستش[tex]F(m)=F(m-1) F(m-2) F(m-3) m \Rightarrow[/tex]
[tex]x^{3}-x^{2}-x-1=0[/tex]
اگر کسی بتونه ریشه های این معادله رو به دست بیاره اولا بهش تبریک میگم دوما قطعا به راحتی به جواب این مسئله میرسه خب میریم سراغ روش دوم یعنی درخت بازگشت و هزینه سطوح درخت به صورت زیر است
[tex]{\color{Red} (n \frac{n7}{8} \frac{n63}{64} ...)}[/tex]
اینجا کار یه کم سخته ولی باز یه قاعده هستش که ما رو کمک میکنه این قاعده رو در CLRS بهش اشاره شده و فک کنم آقای یوسفی هم بهش اشاره کرده :
[tex](\frac{1}{2} \frac{1}{4} \frac{1}{8} \frac{1}{16} ...) = c[/tex]
این قضیه داره میگه که جمع این سری همیشه یه عدد ثابت میشه و این باعث میشه که سری زیر به این صورت حل بشه
[tex]n \frac{n}{2} \frac{n}{4} \frac{n}{8} ...= n(1 \frac{1}{2} \frac{1}{4} \frac{1}{8} \frac{1}{16} ...) = nc=\theta (n)[/tex]
حواسمون باشه که این با سری [tex]n(1 \frac{1}{2} \frac{1}{3} \frac{1}{4} \frac{1}{5} ...) = \theta (nlogn)[/tex] تفاوت داره چون سری اعداد اینجا خیلی بزرگتر هستش
و در ادامه اگر به سری اعداد خودمون توجه کنیم میبینیم که از سری اعداد [tex]\frac{1}{2} \frac{1}{4} \frac{1}{16} \frac{1}{32} ... [/tex] خیلی کوچیکتره و
[tex] {\color{Red}n(1 \frac{7}{8} \frac{63}{64} ...)=nc=\theta (n)}[/tex]
۰
ارسال: #۴
RE: دو تست از پیچیدگی زمانی
سلام . این دو تا تست یه مدت فکر من رو هم مشغول کرده بودند. هنوز هم نمیدونم درست فهمیدم یا نه!!!
تو پاسخنامه گفته : در سوال ۵۹ فرم خود تابع داده شده اما توی سوال ۶۰ فرم پیچیدگی تابع و این دو همیشه مثل هم نیستند!
پس در سوال ۶۰ نمیتونیم از ترسیم درخت بازگشتی و شمارش گره ها استفاده کنیم . سوال ۶۰ رو با جایگذاری حل کرده
این چیزی بود که من خوندم ولی هنوز هم خودم اشکال دارم.
تو پاسخنامه گفته : در سوال ۵۹ فرم خود تابع داده شده اما توی سوال ۶۰ فرم پیچیدگی تابع و این دو همیشه مثل هم نیستند!
پس در سوال ۶۰ نمیتونیم از ترسیم درخت بازگشتی و شمارش گره ها استفاده کنیم . سوال ۶۰ رو با جایگذاری حل کرده
این چیزی بود که من خوندم ولی هنوز هم خودم اشکال دارم.
۰
ارسال: #۵
دو تست از پیچیدگی زمانی
آره. اما منم نمیدونم چه زمانی باید تعداد گره‌ها شمرده شه و چه موقع باید برای هر گره مقداری که جمع میشه باهاش رو هم حساب کرد!
۰
ارسال: #۶
دو تست از پیچیدگی زمانی
ممنون جاوا جان.
پس نتیجه اینکه توی جاهایی که تابع داده، توی درخت باید فقط تعداد گره‌ها رو بشماریم، فارق از اینکه آخرش با چه چیزی جمع میشه.
اما توی جاهایی که رابطه بازگشتی داده، باید برای هر سطر از درخت اون مقداری که جمع میشه رو حساب کرد و به اندازه‌ی ارتفاع با هم جمع کرد.
پس نتیجه اینکه توی جاهایی که تابع داده، توی درخت باید فقط تعداد گره‌ها رو بشماریم، فارق از اینکه آخرش با چه چیزی جمع میشه.
اما توی جاهایی که رابطه بازگشتی داده، باید برای هر سطر از درخت اون مقداری که جمع میشه رو حساب کرد و به اندازه‌ی ارتفاع با هم جمع کرد.
۰
ارسال: #۷
دو تست از پیچیدگی زمانی
پیرو فرمایشات دوست خوبم اقای 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.
ممنون از لطفت.
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.
ممنون از لطفت.
ارسال: #۹
RE: دو تست از پیچیدگی زمانی
(۰۹ دى ۱۳۹۱ ۰۹:۵۸ ب.ظ)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.
ممنون از لطفت.
ارسال: #۱۰
RE: دو تست از پیچیدگی زمانی
(۰۹ دى ۱۳۹۱ ۰۹:۵۸ ب.ظ)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]
ارسال: #۱۱
RE: دو تست از پیچیدگی زمانی
نه ببین این زمان یک درخت به ارتفاع n که هر گره دوتا گر داره تا اینجا میشه [tex]2^n[/tex]
هزینه هر مرحله هم که lgn . پس میشه [tex](2^n)\log n[/tex]
هزینه هر مرحله هم که lgn . پس میشه [tex](2^n)\log n[/tex]
۰
ارسال: #۱۲
دو تست از پیچیدگی زمانی
در تست اول زمان اجرایی تابع رو خواسته. دقت کن که معنیش میشه چند بار تابع اجرا میشه؟؟؟ وقتی که ازت میپرسه چند بار تابع داره اجرا میشه دیگه n رو چرا در نظر بگیری؟؟ مثل این میمونه بهت بگن تو چند ساعت درس خوندی؟ بگی من ۴ ساعت خوندم و توی هر ساعت ۱۰ صفحه.(۱۰ رو همون n فرض کن) . بعد بگی پس من ۴*۱۰ = ۴۰ ساعت درس خوندم!!!!!!
در تست دوم تابع زمان رو داده نه تابع مسئله. یعنی اصلا مسئله یه چیزی دیگه بوده حالا تابع زمانش شده این. اینجا n تاثیر گذاره. مثال اینجا این میشه که بهت میگن چند ساعت درس خوندی؟ میگی ۱۰ صفحه خوندم(این ۱۰ همون n میشه) هر صفحه ۱ ساعت طول کشیده پس ۱*۱۰=۱۰ ساعت خوندم.
در تست دوم تابع زمان رو داده نه تابع مسئله. یعنی اصلا مسئله یه چیزی دیگه بوده حالا تابع زمانش شده این. اینجا n تاثیر گذاره. مثال اینجا این میشه که بهت میگن چند ساعت درس خوندی؟ میگی ۱۰ صفحه خوندم(این ۱۰ همون n میشه) هر صفحه ۱ ساعت طول کشیده پس ۱*۱۰=۱۰ ساعت خوندم.
۰
ارسال: #۱۳
Re: دو تست از پیچیدگی زمانی
درسته... مرسی.
اون دومی هم میشه ۲ به توان Lg n اره؟
و این هم آخریش:
T(n)=T(n/2)+T(n/4)+T(n/8)+n
ممنون میشم اینو هم جواب بدید.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
اون دومی هم میشه ۲ به توان 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!!!
چه سریع جواب دادن بچه ها
یه قسمتی رو پاک کردم دیگه!
خیلی جالب شد!
تو کتاب شما سوال مربوط به دولتی ۷۴ و آزاد ۸۴ رو مشابه فرض کرده
ولی آقای یوسفی تو کتاب ساختمان سوال دولتی ۷۴ رو زده و گفته از مرتبه n هست
ولی تو طراحی الگوریتم آزاد ۸۴ رو زده و گفته از مرتبه n*2!!!
چه سریع جواب دادن بچه ها
یه قسمتی رو پاک کردم دیگه!
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close