بهتر بود سوالا رو می ذاشتین .اسکن میکردین یا عکس می گرفتین. من کتابش رو ندارم.

چند نکته رو خیلی خلاصه خدمت شما دوست عزیزم unification بگم:

۱- شما یکبار دیگه با دقت تمام و کامل، درس فصل اول رو از همون پوران که فرمودید بخونید.
۲-Ln همون logn هستش منتها با مبنای e
۳- به لحاظ مرتبه و رشد‌، لگاریتم های با مبناهای مختلف یکسان هستند یعنی هم رشدند.
۴- اگه فقط نوشتند lgn معمولا مبنا ۲ هستش.
۵- اپسیلون یک عدد خیلی کوچک و مثبت زیر یک است و می تونیم مثلا ۰/۲ بگیریم.
۶- در استفاده از حد برای تعیین رشد تابع‌، در واقع از همون مفهوم حد بی نهایت در توابع کسری استفاده می کنیم. که خود پوران در درس مثال زده.
۷- در مورد یافتن مرتبه یک شبه کد مثل حلقه و ... شما باید قوه‌ی تحلیل و خلاقیت خود رو در این زمینه بالا ببرید‌، یعنی هرچه شما نمونه های بیشتری ببینید دیگه تیپ سوالات دستتون می آد. پوران هم مثال های خوبی داره. این سوالات گاها با عددگذاری هم حل می شوند.
۸- در مقایسه رشد توابع می تونیم از روش هایی که هست و گاها ابتکاری سوال رو حل کنیم.
۹- CLRS هم در این مورد خوبه.
اگه خواستید سوالات مد نظرتون رو قرار بدید‌، تا جایی که بتونیم در خدمتیم.
یا علی(ع)

مرتبه زمانی

تعداد تکرار X++ (با فرض n>=3 فقط برای همین سوال)






چجوری حل میشه؟

کدام صحیح است


کامپیوتری در واحد زمان مسئله ایی به اندازه ۱۶ را که الگوریتم ان از مرتبه زمانی n.2^n است حل میکند. اگرسرعت کامپیوتر ۱۳۱۰۷۲ => 2^7 برابر گردد این کامپیوتر همان مساله را با چه اندازه ایی در واحد زمان حل خواهد کرد ؟

دوست عزیز جواب هایی که من می دم چیزی که خودم تحلیل کردم پس می تونه درست نباشه
سوال ۱
حلقه‌ی اول دز Lgn اجرا میشه و حلقه‌ی دوم و حلقه آخر هم در ...+۴+۲+۱ اجرا میشه که متناسب با ۲^n است پس میشه گفت کد از مرتبه ی[tex]\theta (n^{2}lgn)[/tex]
است

---

(۰۵ آبان ۱۳۹۰ ۰۴:۲۵ ب.ظ)unification نوشته شده توسط:  چجوری حل میشه؟

کد:

n^2sin n =O(n)

به نظر من این تساوی درست نیست چون اگه بنویسیم[tex]lim \frac{n^{2}sinn}{n}=lim n^{2} =\infty[/tex]
و این حد این رو نشون میده که صورت کسر سرعت افزایشش بیشتره یعنی نمی تونه از [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]
است