سلام.
تست ۲۱
تستهایی که اپسیلون دارند چطور حل میشن.؟
چطوری باید عدد گذاری کنیم ؟چه عددایی؟اونوقت اگه تتا وجود داشته باشه چی؟
استفاده از حد برای تعیین رشد تابع چگونه است ؟
تست ۲۹
LN فرقش با Lg چیه و چجوری حل میشن ؟
تو خیلی از سوالات این فصل logn نوشته ولی طبق Lg عمل میکنه (یعنی مبنا ۱۰ مینویسه ولی ۲) .. یادرسته . و من اشتباه میکنم؟ ار کجا بفهمیم که هربار کدوم مد نظر طراحه ؟
تست ۳۱
گام حلقه for بعد از اجرای اول حلقه . ثابت میشه یا اینکه میشه تو حلقه گام حلقه رو هم تغییر داد ؟
و بعدمیتونید تو فهم تستای زیر کمک کنید ؟
۱۹ ۲۰ ۲۱ ۲۵ ۲۶ ۲۸ ۲۹ ۳۰ ۳۱
ممنونم
بهتر بود سوالا رو می ذاشتین .اسکن میکردین یا عکس می گرفتین. من کتابش رو ندارم.
چند نکته رو خیلی خلاصه خدمت شما دوست عزیزم unification بگم:
۱- شما یکبار دیگه با دقت تمام و کامل، درس فصل اول رو از همون پوران که فرمودید بخونید.
۲-Ln همون logn هستش منتها با مبنای e
۳- به لحاظ مرتبه و رشد، لگاریتم های با مبناهای مختلف یکسان هستند یعنی هم رشدند.
۴- اگه فقط نوشتند lgn معمولا مبنا ۲ هستش.
۵- اپسیلون یک عدد خیلی کوچک و مثبت زیر یک است و می تونیم مثلا ۰/۲ بگیریم.
۶- در استفاده از حد برای تعیین رشد تابع، در واقع از همون مفهوم حد بی نهایت در توابع کسری استفاده می کنیم. که خود پوران در درس مثال زده.
۷- در مورد یافتن مرتبه یک شبه کد مثل حلقه و ... شما باید قوه‌ی تحلیل و خلاقیت خود رو در این زمینه بالا ببرید، یعنی هرچه شما نمونه های بیشتری ببینید دیگه تیپ سوالات دستتون می آد. پوران هم مثال های خوبی داره. این سوالات گاها با عددگذاری هم حل می شوند.
۸- در مقایسه رشد توابع می تونیم از روش هایی که هست و گاها ابتکاری سوال رو حل کنیم.
۹- CLRS هم در این مورد خوبه.
اگه خواستید سوالات مد نظرتون رو قرار بدید، تا جایی که بتونیم در خدمتیم.
یا علی(ع)
مرتبه زمانی
کد:
for(i=1;i<=n;i=i*2)
for(j=1;j<=n;j=j*2)
for(k=1;k<=j;k++)
x++;تعداد تکرار X++ (با فرض n>=3 فقط برای همین سوال)
کد:
for(i=3;i<=n;i=i*2)
x++;کد:
for(i=1;i<=n;i++)
for(j=1;j<=n;j=j+i)
x++;کد:
for(i=1 to n)
for(j=n to i)
for(k=1 to n^2)
sum=sum+Aچجوری حل میشه؟
کد:
n^2sin n =O(n)کدام صحیح است
کد:
n^3logn=O((3+K))
n(1+k)=O(nlogn)
۰<k<0.1
k= همان اپسیلون استکامپیوتری در واحد زمان مسئله ایی به اندازه ۱۶ را که الگوریتم ان از مرتبه زمانی n.2^n است حل میکند. اگرسرعت کامپیوتر ۱۳۱۰۷۲ => 2^7 برابر گردد این کامپیوتر همان مساله را با چه اندازه ایی در واحد زمان حل خواهد کرد ؟
دوست عزیز جواب هایی که من می دم چیزی که خودم تحلیل کردم پس می تونه درست نباشه
سوال ۱
حلقه‌ی اول دز Lgn اجرا میشه و حلقه‌ی دوم و حلقه آخر هم در ...+۴+۲+۱ اجرا میشه که متناسب با ۲^n است پس میشه گفت کد از مرتبه ی[tex]\theta (n^{2}lgn)[/tex]
است
(۰۵ آبان ۱۳۹۰ ۰۴:۲۵ ب.ظ)unification نوشته شده توسط: چجوری حل میشه؟به نظر من این تساوی درست نیست چون اگه بنویسیم[tex]lim \frac{n^{2}sinn}{n}=lim n^{2} =\infty[/tex]
کد:
n^2sin n =O(n)
و این حد این رو نشون میده که صورت کسر سرعت افزایشش بیشتره یعنی نمی تونه از [tex]\bigcirc (n)[/tex]
باشه
(۰۷ آبان ۱۳۹۰ ۱۲:۲۴ ق.ظ)ahmadnouri نوشته شده توسط:به نظر منکد:
for(i=1 to n)
for(j=n to i)
for(k=1 to n^2)
sum=sum+A
حلقه‌ی دوم درصورتی اجرا میشه که n = i باشه و اگه این چنین باشه حلق‌ی سوم هم ۲^n اجرا میشه کلا کد از مرتبه‌ی [tex]\theta (n^{2})[/tex]
است