دوستان ممنون میشم راهنماییم کنید
من نمیدونم چذا داخل این فصل ۱ ساختمان گیر افتادم مخصوصا با یا قضیه اصلی
جواب سوال سوم رو می‌نویسم.
فرض کنید که عبارت [tex]\frac{n^2}{\lg n}=O(n)[/tex] درست باشه. در اینصورت باید به ازای یک مقدار ثابت c نامساوی [tex]\frac{n^2}{\lg n}\leq cn[/tex] برقرار باشه. حالا اگر طرفین این نامساوی رو تقسیم بر n کنیم داریم [tex]\frac{n}{\lg n}\leq c[/tex] و این یعنی مقدار c یک مقدار ثابت نیست و درنتیجه فرض اولیه ما یعنی [tex]\frac{n^2}{\lg n}=O(n)[/tex] غلطه.
سلام. من هم سوال یک رو پاسخ می دم.
---------------------------------------------
ببین وقتی می گه مرتبه اجرای الگوریتم زیر چیست، باید دنبال یک دستور خاص بگردی که اون دستور تابع یا تحت امر درجه ورودی الگوریتم باشه. مثلا تو جست و جوی خطی دستور اصلی همون مقایسه عنصر کلید با عناصر دیگه یا همون دستور if داخلی هست، یا مثلا در همین مثال خودت دستور اصلی ای وجود نداره، منظورش تعداد باری که کل الگوریتم اجرا میشه هست. حلقه while اول دقیقا n+1 بار اجرا میشه (اون یک بار برای آخرین مرحله ست که ببینه باز شرط درسته یا نه) توجه کن که گام حرکت تو این حلقه یکبار یکبار است i = i+1.
حالا حلقه داخلی رو ببین، تعداد گامهای حرکتش رو بگم که هربار ضربدر ۲ میشه یعنی ۱ ۲ ۴ ۸ ۱۶ ... پس چون هربار گام حرکت دوبرابر میشه، logn باید استفاده کنیم. اما این حلقه while هم یک بار اضافی اجرا میشه(مث قبلی که آخرین دفعه برای بررسی شرط که ببینه آیا باید ادامه بده یا نه).
خب تا اینجا که مشکلی نیس! چون دوحلقه تودر تو هستن پس درهم ضرب می N+1 * logn+1 (اون لگاریتم بعلاوه یک رو داخل پرانتز هستن) که میشه تتای nlogn.
موفق باشی.
--------------------------------------------------------------------------------
من متوجه نشدم.
لطفا توضیح بدید اینو :
اولا "این یعنی مقدار c یک مقدار ثابت نیست."
=
دوما : چه ربطی به فرض اولیه مسئله داشت
=
سلام دوستان خیلی ممنون که وقت گذاشتین
میشه بیشتر توضیح بدین مخصوصا سوال ۱ را ممنون میشم
حلقه بیرونی N +1
حلقه داخلی LOG N+1 ( البته داخل کتاب مقسمس گفته LOGN+2 بار
n+1*logn+1
logn +1 باید داخل پرانتز باشد
که میشه nlogn+n+logn+1
داخل کتاب پوران گفته جواب میشه n * (logn+1 )
این روش که فقط تعداد مراحل اجرای حلقه داخلی را بدست میاره . وقتی میگه f(n را بدست بیارین باید تعداد مراحل داخلی ترین دستور را بدست بیاریم ؟ با نه؟
اساتید راهنمایی بفرمایید لطفا ، سوال ۳۰ فصل ۱ چاپ ۸۹ ساختمان پوران (تست ۸۷ آی تی ) رو با عدد گزاری حل کرده . میگه به ازای n=3 یکبار اجرا میشه پس گزینه ۳ در حالی که گزینه ۲ همین سوال هم به ازای ۳ یکبار اجرا میشه.
۳۰- در کد زیر دستور ++x چندبار اجرا می شود:
[tex]for(i=3;i<=n;i=i*2)[/tex]
[tex]x [/tex]
[tex]1)\left \lfloor logn\frac{n}{3} \right \rfloor 2)\left \lceil \frac{(logn)}{3} \right \rceil 3)\left \lfloor logn\frac{n}{3} 1 \right \rfloor 4)\left \lceil \frac{(logn 1)}{3} \right \rceil[/tex]
(۱۹ شهریور ۱۳۹۲ ۰۶:۰۰ ب.ظ)ttiiko نوشته شده توسط: اساتید راهنمایی بفرمایید لطفا ، سوال ۳۰ فصل ۱ چاپ ۸۹ ساختمان پوران (تست ۸۷ آی تی ) رو با عدد گزاری حل کرده . میگه به ازای n=3 یکبار اجرا میشه پس گزینه ۳ در حالی که گزینه ۲ همین سوال هم به ازای ۳ یکبار اجرا میشه.
۳۰- در کد زیر دستور ++x چندبار اجرا می شود:
[tex]for(i=3;i<=n;i=i*2)[/tex]
[tex]x [/tex]
[tex]1)\left \lfloor logn\frac{n}{3} \right \rfloor 2)\left \lceil \frac{(logn)}{3} \right \rceil 3)\left \lfloor logn\frac{n}{3} 1 \right \rfloor 4)\left \lceil \frac{(logn 1)}{3} \right \rceil[/tex]
سلام.
هر تاپیک فقط باید حاوی یک سوال باشه. لطفا بیشتر دقت کنید. ممنون.
به ازای n=12 تنها ۳ بار دستور x++ اجرا میشه که تنها در گزینه ۲ این جواب مشهود است.
موفق باشید.
سلام
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سوال ۳ به محدوده جوابی که به دست میاد دقت کنید.
بنظرم اول بیاید سوالات حل شده تو مانشت رو بررسی کنید . بعدش اگه سوالی بود بپرسید. اینطوری بهتره تا یه فصل رو بزارید وسط هر کسی بیاید یه سوالش رو حل کنه .
تاپیک بسته میشه