تحلیل مرتبه زمانی دو الگوریتم - نسخه‌ی قابل چاپ

تحلیل مرتبه زمانی دو الگوریتم - H-Arshad - 07 آذر ۱۳۹۵ ۱۱:۵۲ ب.ظ سلام بچه ها این دو الگوریتم میشه بگید چجوری حساب کرده؟ اخه داخل سیگما log هست و من تریس میکنم اصلا جور در نمیاد توروخدا کمک

RE: تحلیل مرتبه زمانی دو الگوریتم - Saman - 07 آذر ۱۳۹۵ ۱۱:۵۸ ب.ظ سلام اینو ببین مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

RE: تحلیل مرتبه زمانی دو الگوریتم - H-Arshad - 08 آذر ۱۳۹۵ ۰۱:۳۸ ق.ظ راستش محاسبه و ریاضی اش به کنار...من اصلا نمیدانم تحیلیش رو چرا این جور نوشته؟

RE: تحلیل مرتبه زمانی دو الگوریتم - H-Arshad - 08 آذر ۱۳۹۵ ۱۲:۵۸ ب.ظ راستش مشکل من با این هست که چون حلقه داخلی در عدد ۲ ضرب میشه پس گفتیم گام اون لگاریتمی هست درسته؟ الان در سیگما گفته logi یعنی پس لگاریتم اعداد ۳ ۵ ۷ ۹ ۱۱ ۱۳ ۱۵ ۱۷ و ... هم توش حساب میشه... و این جور جمع ش عوض میشه

RE: تحلیل مرتبه زمانی دو الگوریتم - Saman - 08 آذر ۱۳۹۵ ۰۲:۰۶ ب.ظ سلام ببینید، شما i=1 قرار میدهید. بعد به حلقه ی داخلی وارد میشوید. و به اندازه ی i حلقه ی داخلی رو اجرا میکنید. بعد دقت کنید که خود i میتونه تا n اجرا بشه. ۱)فرض کنیم i=1 باشد.شما j را یک بار اجرا میکنید دستور بعدی آن را هم اجرا کرده از حلقه خارج میشوید. === ۲)حالا i=2 باشد ، شما از j=1 تا زمانی که j<=2 باشد حلقه ی داخلی را اجرا میکنید. فقط دقت کنید که وقتی در این حلقه میچرخید j هر بار دو برابر می شود. حالا به ازای j=1 شرط برقرار است و یک اجرا داریم.سپس شما j*=2 را انجام دهید که مقدار j=2 میشود. باز هم شرط حلقه برقرار است و یک اجرای دیگر نیز داریم.(این شد دو تا اجرا) در چرخش بعد در داخل همین حلقه شرط دیگر برقرار نیست. و از حلقه خارج میشویم. ۳) سپس i=3 میشود باز هم به حلقه ی داخلی وارد می شویم.و به ازای j=1 تا زمانی که j<=3 به اجرای حلقه می پردازیم، چون j هر بار دو برابر میشود باز هم با دو اجرا از حلقه داخلی خارج میشویم. ۴)سپس i=4 باز هم به حلقه ی داخلی وارد می شویم و به ازای j=1 تا زمانی که j<=4 به اجرای حلقه می پردازیم داریم، به ازای j=1 شرط برقرار است و یک اجرا داریم، سپس j*=2 میشود و باز هم شرط برقرار است به شکل مقابل ( ۴=>2 ) ، سپس دوباره j*=2 را انجام میدهیم و باز هم شرط برقرار است یعنی داریم ( ۴>=4) ، یعنی سه اجرا به ازای i=4 در دور بعدی از حلقه خارج می شویم . . . ۵)مقدار i=5 الی آخر . . . به صورت تقریبی میشود حدس زد که ما مجموعِ [tex]\log i[/tex] تا اجرا داریم. با حد بالای n ، چرا که i خودش تا n پیش میرود . . . زمان اجرا ها به ازای مقادیر i : [tex]1\: +2+2+3+3\: .\: .\: .[/tex] همین که در حلقه داخلی j هر بار دو برابر میشود و حد بالای j را i در نظر گرفته ایم یعنی اینکه به اندازه ی مجموع لگاریتم i با حدود i به اجرای حلقه داخلی j می پردازیم.